Submission #2545782

---

Source Code Expand

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1LL << 30;
int MOD = 1e9+7;
const int MAX_N = 100010;
struct UnionFind{
    int par[MAX_N];
    void init(int n){
        for(int i = 0;i < n;i++)par[i] = i;
    }
    int root(int x){
        if(par[x] == x)return x;
        else return par[x] = root(par[x]);
    }
    bool same(int x,int y){
        return root(x) == root(y);
    }
    void unite(int x,int y){
        x = root(x);
        y = root(y);
        if(x == y)return;
        par[y] = x;
    }
};
main(){
    int N,M;
    cin >> N >> M;
    if(M == 0){
        cout << "Yes" << endl;
        return 0;
    }
    vector<int> L(M),R(M),D(M);
    UnionFind uf;
    uf.init(N);
    for(int i = 0;i < M;i++){
        cin >> L[i] >> R[i] >> D[i];
        L[i]--,R[i]--;
        uf.unite(L[i],R[i]);
    }
    vector<vector<int> > V(N);
    for(int i = 0;i < N;i++){
        V[uf.root(i)].push_back(i);
    }
    for(int i = 0;i < N;i++){
        map<int,int> mp;
        mp[uf.root(i)] = 0;
        for(auto num:V[i]){
            if(mp.find(R[num]) != mp.end() && mp.find(L[num]) != mp.end()){
                if(mp[ R[num] ] - mp[ L[num] ] != D[num]){
                    cout << "No" << endl;
                    return 0;
                } 
            }
            mp[ R[num] ] = mp[ L[num] ] + D[num];
        }
    }
    cout << "Yes" << endl;
}

Submission Info

Judge Result