Consistent Ave

2 secs 1024 MB

shinnshinn

問題

提出

テストケース

解説

証言をもとにグラフを作成することができます。

各連結成分ことに、１人を０点とすることによりその連結成分内の人の点数が一意に定まります。

DFS/BFSを行います。

各頂点から別の頂点へ移動する時、まだ訪れていない頂点であれば点を定め、すでに訪れている頂点であれば点差が正しいかを判定します。そして、その連結成分内での最大値と最小値が $10^9$ 以下であるかを確認すればよいです。

また、重みつきUFでも解くことができます。実装例

実装

Rust

xxxxxxxxxx
 
use std::collections::VecDeque;
use proconio::{*, marker::Usize1};
​
#[derive(Clone)]
struct Edge {
    to: usize,
    c: i64,
}
​
fn main() {
    input! {
        n: usize,
        m: usize,
        xyv: [(Usize1, Usize1, i64); m],
    }
​
    let mut es = vec![vec![]; n];
    for &(x, y, v) in &xyv {
        es[x].push(Edge {to: y, c: v });
        es[y].push(Edge {to: x, c: -v });
    }
​
    let max_score = 1e9 as i64;
​
    let mut visited = vec![false; n];
    let mut score = vec![0; n];
    for i in 0..n {
        if visited[i] { continue; }
        let mut mx = 0;
        let mut mi = 0;
        let mut que = VecDeque::new();
        que.push_back((i, 0));
        while let Some((v, s)) = que.pop_front() {
            if visited[v] { 
                if s != score[v] {
                    println!("No");
                    return;
                }
                continue;
            }
            mx = mx.max(score[v]);
            mi = mi.min(score[v]);
            visited[v] = true;
            for e in &es[v] {
                if visited[e.to] {
                    if score[e.to] != score[v] + e.c {
                        println!("No");
                        return;
                    }
                } else {
                    score[e.to] = score[v] + e.c;
                    que.push_back((e.to, score[e.to]));
                }
            }
        }
​
        if mx-mi > max_score {
            println!("No");
            return;
        }
    }
​
    println!("Yes");
}
​

C++

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
int main() {
    int n,m; cin >> n >> m;
    vector<vector<pair<int, ll>>> g(n);
    for(int i=0; i<m; i++) {
        ll u,v,c; cin >> u >> v >> c;
        g[u-1].emplace_back(v-1, -c);
        g[v-1].emplace_back(u-1, c);
    }
    ll INF = 1000000000000000LL;
    vector<ll> potential(n, -INF);
    for(int i=0; i<n; i++) {
        if (potential[i] != -INF) continue;
        ll mn = INF;
        ll mx = -INF;
        auto dfs = [&] (auto self, int x, ll pi) -> bool {
            if (potential[x] != -INF) return potential[x] == pi;
            mn = min(mn, pi);
            mx = max(mx, pi);
            potential[x] = pi;
            for(auto [y, cost] : g[x]) {
                if (!self(self, y, pi + cost)) return false;
            }
            return true;
        };
        if (!dfs(dfs, i, 0)) {
            cout << "No\n";
            return 0;
        }
        if (mx - mn > 1000000000) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
}
​