Submission #2029402


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/




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;
}

Submission Info

Submission Time
Task D - People on a Line
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2779 Byte
Status
Exec Time 108 ms
Memory 17664 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample01.txt, sample02.txt, sample03.txt, sample04.txt, sample05.txt
All 400 / 400 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 96 ms 17268 KB
02.txt 99 ms 17268 KB
03.txt 79 ms 17536 KB
04.txt 98 ms 17664 KB
05.txt 85 ms 17024 KB
06.txt 75 ms 16512 KB
07.txt 83 ms 17280 KB
08.txt 62 ms 16896 KB
09.txt 61 ms 16256 KB
10.txt 65 ms 16768 KB
11.txt 69 ms 16256 KB
12.txt 62 ms 16256 KB
13.txt 73 ms 16640 KB
14.txt 60 ms 16384 KB
15.txt 62 ms 16256 KB
16.txt 59 ms 16384 KB
17.txt 108 ms 17152 KB
18.txt 100 ms 16768 KB
19.txt 66 ms 16512 KB
20.txt 66 ms 16512 KB
21.txt 87 ms 17152 KB
22.txt 76 ms 16512 KB
23.txt 103 ms 17152 KB
24.txt 56 ms 16512 KB
25.txt 97 ms 17152 KB
26.txt 100 ms 17152 KB
27.txt 69 ms 16000 KB
28.txt 71 ms 16512 KB
29.txt 64 ms 16768 KB
30.txt 76 ms 16768 KB
31.txt 52 ms 16768 KB
32.txt 73 ms 16768 KB
33.txt 81 ms 17152 KB
34.txt 95 ms 17152 KB
35.txt 60 ms 16000 KB
36.txt 76 ms 16512 KB
37.txt 63 ms 16768 KB
38.txt 62 ms 16768 KB
39.txt 52 ms 16768 KB
40.txt 61 ms 16768 KB
41.txt 21 ms 10496 KB
42.txt 28 ms 12416 KB
sample01.txt 4 ms 9728 KB
sample02.txt 4 ms 9728 KB
sample03.txt 4 ms 9728 KB
sample04.txt 4 ms 9728 KB
sample05.txt 4 ms 9728 KB