Submission #3594948

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)

using namespace std;
typedef long long int ll;
const ll INF=1e11;
int par[100000]; //親
ll t[100000];
int height[100000];  //木の深さ

void init (int n){
    for (int i=0;i<n;i++){
        par[i]=i;
        height[i]=0;
    }
}
int find (int x){
    if (par[x]==x){
        return x;
    }
    else{
        return par[x] = find(par[x]);
    }
}
void unite (int x, int y){
    x=find(x);
    y=find(y);
    if (x==y) return;
    
    if (height[x] < height[y]){
        par[x]=y;
    }
    else {
        par[y]=x;
        if (height[x]==height[y]) height[x]++;
    }
}
bool same (int x, int y){
    return find(x) == find(y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N,M;
    cin>>N>>M;
    if (M==0) cout <<"Yes"<<"\n";
    else {
        rep(i,0,N){
            t[i]=INF;
        }
        init (N);
        rep(i,0,M){
            int l,r,d;
            cin>>l>>r>>d;
            l--; r--;
            if (i==0){
                t[l]=0;
                t[r]=d;
                unite(l,r);
            }
            else {
                if (same(l,r)){
                    if (t[r]-t[l]!=d){
                        cout << "No" <<"\n";
                        return 0;
                    }
                }
                else {
                    if (t[l]==INF&&t[r]==INF){
                        t[l]=0; t[r]=d;
                    }
                    if (t[l]!=INF&&t[r]==INF){
                        t[r]=t[l]+d;
                    }
                    if (t[l]==INF&&t[r]!=INF){
                        t[l]=t[r]-d;
                    }
                    else {
                        rep(i,0,N){
                            if (same(i,r)) t[i]+=t[r]-t[l]-d;
                        }
                    }
                    unite(l,r);
                }
            }
        }
        cout <<"Yes"<<"\n";
    }
}

Submission Info

Judge Result