People on a Line [AtCoder Regular Contest 090 D]

https://beta.atcoder.jp/contests/arc090/tasks/arc090_b

解説

https://beta.atcoder.jp/contests/arc090/submissions/2029402

重要な考察があり、「1つ数を決めるとそれと連結の座標の数が全て決まる」
座標のまだ数が決まってない所の1つを0にして、
有向辺(a,b,c)を順にたどって行く場合は「col[b] = col[a] + c」、
逆に辿っていく場合は「col[a] = col[b] - c」で数を決めていく。
このように構築していく仮定で矛盾が発生したら"No"を返す。
全て問題無く構築できたら"Yes"を返す。

int N, M;
vector<pair<int, int>> E[201010];
vector<pair<int, int>> EE[201010];
int vis[201010], col[201010];
//---------------------------------------------------------------------------------------------------
#define no "No"
#define yes "Yes"
string solve() {
    rep(i, 0, N) if (!vis[i]) {
        col[i] = 0;
        vis[i] = 1;
        queue<int> que;
        que.push(i);
        while (!que.empty()) {
            int q = que.front(); que.pop();
 
            fore(p, E[q]) {
                if (vis[p.first]) {
                    if (col[q] + p.second != col[p.first]) return no;
                } else {
                    col[p.first] = col[q] + p.second;
                    vis[p.first] = 1;
                    que.push(p.first);
                }
            }
 
            fore(p, EE[q]) {
                if (vis[p.first]) {
                    if (col[q] - p.second != col[p.first]) return no;
                }
                else {
                    col[p.first] = col[q] - p.second;
                    vis[p.first] = 1;
                    que.push(p.first);
                }
            }
        }
    }
 
    return yes;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        E[a].push_back({ b, c });
        EE[b].push_back({ a, c });
    }
    cout << solve() << endl;
}