Submission #2030899

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define NDEBUG
#include "cout11.h"
#endif
#undef NDEBUG
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

class UnionFind {
  vector<int> data;
 public:
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};


int N, M;
vvi f;
map<int, vi> mv;
vector<vector<ii>> arc;
vi loc;
vector<bool> locset;

bool sub(int rt){
    int p1 = mv[rt][0];
    set<int> vis;
    vis.insert(p1);

//    vi loc(N);
//    vector<bool> locset(N, false);

    loc[p1] = 0; // 基準
    locset[p1] = true;

    queue<int> q;
    for (auto p: arc[p1]) {
        loc[p.first] = loc[p1] + p.second;
        locset[p.first] = true;
        q.push(p.first);
    }

    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (found(vis, x)) continue;

        for (auto p : arc[x]) {
            if (locset[p.first]) {
                if (loc[p.first] != loc[x] + p.second) return false;
            } else {
                loc[p.first] = loc[x] + p.second;
                locset[p.first] = true;
                if (!found(vis, p.first)) q.push(p.first);
            }
        }
    }
#ifdef DEBUG
    for (int i : mv[rt]) {
        printf("(%d:%d)%c", i, loc[i], locset[i]?' ':'x');
    }
    printf("\n");
#endif

    return true;
}

bool solve(){
    arc.resize(N);

    loc.resize(N);
    locset.assign(N, false);

    UnionFind uf(N);
    rep(i,M) {
        int li = f[i][0], ri = f[i][1], di = f[i][2];
        uf.unionSet(li, ri);
        arc[li].pb(ii(ri, di));   // ri = li + di
        arc[ri].pb(ii(li, -di));  // li = ri - di
    }

    rep(i,N) {
        int rt = uf.root(i);
        mv[rt].pb(i);
    }

    for (auto p: mv){
        int rt = p.first;
        if (!sub(rt)) return false;
    }

    return true;
}

int main() {
    cin>>N>>M;
    f.resize(M);
    rep(i,M){
        int li, ri, di; cin >> li >> ri >> di;
        f[i] = { li-1, ri-1, di };
    }
    cout << (solve() ? "Yes" : "No") << endl;
    return 0;
}

Submission Info

Submission Time
Task D - People on a Line
User naoya_t
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3353 Byte
Status
Exec Time 209 ms
Memory 21500 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 197 ms 21236 KB
02.txt 201 ms 21240 KB
03.txt 203 ms 21372 KB
04.txt 209 ms 21500 KB
05.txt 175 ms 19068 KB
06.txt 153 ms 16888 KB
07.txt 170 ms 18680 KB
08.txt 143 ms 15992 KB
09.txt 130 ms 15096 KB
10.txt 125 ms 14484 KB
11.txt 131 ms 15100 KB
12.txt 151 ms 16512 KB
13.txt 173 ms 17920 KB
14.txt 134 ms 15484 KB
15.txt 152 ms 16512 KB
16.txt 130 ms 15480 KB
17.txt 189 ms 19960 KB
18.txt 186 ms 18560 KB
19.txt 142 ms 16124 KB
20.txt 146 ms 16124 KB
21.txt 184 ms 19832 KB
22.txt 140 ms 16124 KB
23.txt 185 ms 19832 KB
24.txt 139 ms 16124 KB
25.txt 193 ms 19832 KB
26.txt 187 ms 19832 KB
27.txt 114 ms 13304 KB
28.txt 143 ms 16124 KB
29.txt 113 ms 12916 KB
30.txt 135 ms 15352 KB
31.txt 111 ms 12920 KB
32.txt 137 ms 15352 KB
33.txt 197 ms 19832 KB
34.txt 187 ms 19832 KB
35.txt 113 ms 13304 KB
36.txt 139 ms 16124 KB
37.txt 113 ms 12920 KB
38.txt 133 ms 15352 KB
39.txt 107 ms 12920 KB
40.txt 137 ms 15352 KB
41.txt 70 ms 14336 KB
42.txt 91 ms 18560 KB
sample01.txt 1 ms 256 KB
sample02.txt 1 ms 256 KB
sample03.txt 1 ms 256 KB
sample04.txt 1 ms 256 KB
sample05.txt 1 ms 256 KB