Submission #2545866


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 < M;i++){
        V[uf.root(L[i])].push_back(i);
        //V[uf.root(i)].push_back(i);
    }
    /*
    cout << endl;
    for(auto vec:V){
        for(auto i:vec)cout << i << " ";
        cout << endl;
    }
    */
    for(int i = 0;i < N;i++){
        if(V[i].size() <= 1)continue;
        map<int,int> mp;
        mp[ L[ V[i][0] ] ] = 0;
        for(auto num:V[i]){
            //cout << " " << num << endl;
            if(mp.find(R[num]) != mp.end() && mp.find(L[num]) != mp.end()){
                //cout << R[num] << "," << L[num] << endl;
                //cout << mp[ R[num]] << " " << mp[L[num]] << endl;
                if(mp[ R[num] ] - mp[ L[num] ] != D[num]){
                    cout << "No" << endl;
                    return 0;
                } 
            }
            if(mp.find(L[num]) != mp.end())
                    mp[ R[num] ] = mp[ L[num] ] + D[num];
            else    
                    mp[ L[num] ] = mp[ R[num] ] - D[num];

        }
        /*
        cout << i << endl;
        for(auto p:mp){
            cout << p.first << " " << p.second << endl;
        }
        */
    }
    cout << "Yes" << endl;
}

Submission Info

Submission Time
Task D - People on a Line
User Bantako
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2114 Byte
Status WA
Exec Time 166 ms
Memory 6520 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 5
AC × 27
WA × 20
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt
Case Name Status Exec Time Memory
01.txt AC 162 ms 6520 KB
02.txt WA 162 ms 6520 KB
03.txt AC 165 ms 6520 KB
04.txt WA 166 ms 6520 KB
05.txt AC 146 ms 6136 KB
06.txt WA 119 ms 5752 KB
07.txt AC 142 ms 6136 KB
08.txt WA 111 ms 5752 KB
09.txt WA 100 ms 4988 KB
10.txt WA 98 ms 5112 KB
11.txt AC 100 ms 4988 KB
12.txt AC 117 ms 5504 KB
13.txt WA 131 ms 5756 KB
14.txt WA 104 ms 5116 KB
15.txt AC 116 ms 5504 KB
16.txt AC 105 ms 5240 KB
17.txt WA 154 ms 6264 KB
18.txt WA 141 ms 6016 KB
19.txt WA 121 ms 5752 KB
20.txt WA 113 ms 5752 KB
21.txt AC 151 ms 6264 KB
22.txt AC 120 ms 5752 KB
23.txt AC 149 ms 6264 KB
24.txt AC 112 ms 5752 KB
25.txt WA 156 ms 6264 KB
26.txt WA 149 ms 6264 KB
27.txt WA 88 ms 4732 KB
28.txt WA 112 ms 5752 KB
29.txt WA 87 ms 4732 KB
30.txt WA 105 ms 5116 KB
31.txt WA 87 ms 4732 KB
32.txt WA 105 ms 5116 KB
33.txt AC 157 ms 6264 KB
34.txt AC 149 ms 6264 KB
35.txt AC 87 ms 4732 KB
36.txt AC 112 ms 5752 KB
37.txt AC 88 ms 4732 KB
38.txt AC 106 ms 5240 KB
39.txt AC 88 ms 4856 KB
40.txt AC 106 ms 5240 KB
41.txt AC 1 ms 256 KB
42.txt AC 54 ms 4348 KB
sample01.txt AC 1 ms 256 KB
sample02.txt AC 1 ms 256 KB
sample03.txt AC 1 ms 256 KB
sample04.txt AC 1 ms 256 KB
sample05.txt AC 1 ms 256 KB