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