Submission #3040820


Source Code Expand

#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define REP(i,n) for(int i = 0; i < int(n); i++)
#define REREP(i,n) for(int i = int(n - 1); i >= 0; i--)
#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define REFOR(i, m, n) for(int i = int(n - 1);i >= int(m);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define fi first 
#define se second

#define VI vector<int>
#define VVI vector<vector<int>>
#define VVVI vector<vector<vector<int>>>
#define VD vector<double>
#define VVD vector<vector<double>>
#define VVVD vector<vector<vector<double>>>
#define VL vector<ll>
#define VVL vector<vector<ll>>
#define VVVL vector<vector<vector<ll>>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define VVVB vector<vector<vector<bool>>>
#define VS vector<string>
#define VVS vector<vector<string>>
#define VVVS vector<vector<vector<string>>>

#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<ll,ll>
#define VPII vector<pair<int,int>>
#define VVPII vector<vector<pair<int,int>>>
#define VVVPII vector<vector<vector<pair<int,int>>>>
#define VPLL vector<pair<ll,ll>>
#define VVPLL vector<vector<pair<ll,ll>>>
#define VVVPLL vector<vector<vector<pair<ll,ll>>>>

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;


void YN(bool flag) {
	cout << ((flag) ? "YES" : "NO") << endl;
}

void Yn(bool flag) {
	cout << ((flag) ? "Yes" : "No") << endl;
}

void yn(bool flag) {
	cout << ((flag) ? "yes" : "no") << endl;
}

template<class T> class Union_Find {
public:
	vector<int> prnt;
	vector<int> rank;
	vector<T> dist;

	Union_Find(int N = 1):prnt(vector<int>(N)),rank(vector<int>(N,0)),dist(vector<int>(N, 0)) {
		for (int i = 0; i < N; ++i) prnt[i] = i;
	}

	int root(int x) {
		if (prnt[x] == x) return x;
		else {
			int r = root(prnt[x]);
			dist[x] += dist[prnt[x]];
			return prnt[x] = r;
		}
	}

	T updated_dist(int x) {
		root(x);
		return dist[x];
	}

	bool same(int x, int y) {
		return root(x) == root(y);
	}

	bool merge(int x, int y, T d) {
		d += updated_dist(x); 
		d -= updated_dist(y);
		x = root(x); y = root(y);
		if (x == y) return false;
		if (rank[x] < rank[y]) {
			swap(x, y);
			d = -d;
		}
		if (rank[x] == rank[y]) ++rank[x];
		prnt[y] = x;
		dist[y] = d;
		return true;
	}

	T diff(int x, int y) {
		return updated_dist(y) - updated_dist(x);
	}
};

int main() {
	int N, M;
	cin >> N >> M;
	Union_Find<int> uf(N);
	for (int i = 0; i < M; ++i) {
		int l, r, d;
		cin >> l >> r >> d;
		--l, --r;
		if (uf.same(l, r)) {
			if (d != uf.diff(l, r)) {
				cout << "No" << endl;
				return 0;
			}
		}
		else {
			uf.merge(l, r, d);
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Submission Info

Submission Time
Task D - People on a Line
User ningenMe
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3190 Byte
Status AC
Exec Time 158 ms
Memory 1408 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 5
AC × 47
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 4 ms 1408 KB
02.txt AC 154 ms 1408 KB
03.txt AC 35 ms 1408 KB
04.txt AC 158 ms 1408 KB
05.txt AC 39 ms 1408 KB
06.txt AC 114 ms 1408 KB
07.txt AC 44 ms 1408 KB
08.txt AC 107 ms 1408 KB
09.txt AC 97 ms 1408 KB
10.txt AC 92 ms 1408 KB
11.txt AC 73 ms 1408 KB
12.txt AC 46 ms 1408 KB
13.txt AC 126 ms 1408 KB
14.txt AC 102 ms 1408 KB
15.txt AC 52 ms 1408 KB
16.txt AC 101 ms 1408 KB
17.txt AC 142 ms 1408 KB
18.txt AC 133 ms 1408 KB
19.txt AC 107 ms 1408 KB
20.txt AC 107 ms 1408 KB
21.txt AC 58 ms 1408 KB
22.txt AC 68 ms 1408 KB
23.txt AC 51 ms 1408 KB
24.txt AC 66 ms 1408 KB
25.txt AC 150 ms 1408 KB
26.txt AC 143 ms 1408 KB
27.txt AC 85 ms 1408 KB
28.txt AC 113 ms 1408 KB
29.txt AC 85 ms 1408 KB
30.txt AC 101 ms 1408 KB
31.txt AC 85 ms 1408 KB
32.txt AC 101 ms 1408 KB
33.txt AC 95 ms 1408 KB
34.txt AC 53 ms 1408 KB
35.txt AC 85 ms 1408 KB
36.txt AC 71 ms 1408 KB
37.txt AC 85 ms 1408 KB
38.txt AC 77 ms 1408 KB
39.txt AC 84 ms 1408 KB
40.txt AC 78 ms 1408 KB
41.txt AC 2 ms 1408 KB
42.txt AC 40 ms 1408 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