Submission #3591214
Source Code Expand
#include <limits.h> #include <algorithm> #include <bitset> #include <cctype> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #include <queue> #define int long long #define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i) #define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i) #define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i) #define REV(i, a, b) for (int i = (a); i >= (b); --i) #define CLR(a, b) memset((a), (b), sizeof(a)) #define DUMP(x) cout << #x << " = " << (x) << endl; #define INF 1001001001001001001ll #define fcout cout << fixed << setprecision(10) using namespace std; struct UnionFind { vector<int> par; vector<int> rank; vector<int> vsize; UnionFind(int size) : par(size), rank(size), vsize(size) { REP(i, size) { par[i] = i; rank[i] = 0; vsize[i] = 1; } } int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } void unite(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (rank[x] < rank[y]) { par[x] = y; } else { par[y] = x; if (rank[x] == rank[y]) rank[x]++; } vsize[x] += vsize[y]; vsize[y] = vsize[x]; } void reset(int x) { par[x] = x; rank[x] = 0; vsize[x] = 1; } bool same(int x, int y) { return find(x) == find(y); } int getSize(int x) { return vsize[find(x)]; } }; vector<int> G[300005]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, M; cin >> N >> M; map<int, vector<pair<int, int>>> C; REP(i, M) { int p, q, c; cin >> p >> q >> c; p--; q--; c--; C[c].push_back({p, q}); } int sz = N; UnionFind uf(N); for (auto kv : C) { int i = kv.first; REP(j, C[i].size()) { auto p = C[i][j]; uf.reset(p.first); uf.reset(p.second); } REP(j, C[i].size()) { auto p = C[i][j]; uf.unite(p.first, p.second); } map<int, int> id; set<int> used; REP(j, C[i].size()) { auto p = C[i][j]; int pp = uf.find(p.first); if (id.count(pp) == 0) id[pp] = sz++; if (used.count(p.first) == 0) { G[id[pp]].push_back(p.first); G[p.first].push_back(id[pp]); } if (used.count(p.second) == 0) { G[id[pp]].push_back(p.second); G[p.second].push_back(id[pp]); } used.insert(p.first); used.insert(p.second); } } vector<int> dp(sz, -1); queue<int> q; dp[0] = 1; q.push(0); while (!q.empty()) { int t = q.front(); q.pop(); REP(i, G[t].size()) { int tt = G[t][i]; if (dp[tt] >= 0) continue; dp[tt] = dp[t] + 1; q.push(tt); } } if (dp[N - 1] < 0) { cout << -1 << endl; } else { cout << dp[N - 1] / 2 << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Snuke's Subway Trip |
User | tatsumack |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 3699 Byte |
Status | AC |
Exec Time | 468 ms |
Memory | 44672 KB |
Judge Result
Set Name | Sample | All | ||
---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||
Status | AC |
|
Set Name | Test Cases |
---|---|
Sample | |
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, sample_01.txt, sample_02.txt, sample_03.txt, w1.txt, w10.txt, w11.txt, w12.txt, w13.txt, w14.txt, w15.txt, w16.txt, w17.txt, w18.txt, w2.txt, w3.txt, w4.txt, w5.txt, w6.txt, w7.txt, w8.txt, w9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 4 ms | 7296 KB |
02.txt | AC | 128 ms | 13312 KB |
03.txt | AC | 407 ms | 44672 KB |
04.txt | AC | 366 ms | 28928 KB |
05.txt | AC | 468 ms | 27056 KB |
06.txt | AC | 245 ms | 21284 KB |
07.txt | AC | 257 ms | 23048 KB |
08.txt | AC | 401 ms | 44544 KB |
09.txt | AC | 199 ms | 20992 KB |
10.txt | AC | 218 ms | 20608 KB |
11.txt | AC | 175 ms | 20740 KB |
12.txt | AC | 70 ms | 12260 KB |
13.txt | AC | 131 ms | 14668 KB |
14.txt | AC | 171 ms | 20840 KB |
15.txt | AC | 155 ms | 23276 KB |
16.txt | AC | 167 ms | 22088 KB |
17.txt | AC | 171 ms | 20712 KB |
18.txt | AC | 106 ms | 13348 KB |
19.txt | AC | 193 ms | 21996 KB |
20.txt | AC | 165 ms | 20204 KB |
21.txt | AC | 302 ms | 35428 KB |
22.txt | AC | 146 ms | 20352 KB |
23.txt | AC | 304 ms | 23836 KB |
24.txt | AC | 166 ms | 19824 KB |
25.txt | AC | 69 ms | 11380 KB |
26.txt | AC | 127 ms | 14820 KB |
27.txt | AC | 150 ms | 19584 KB |
28.txt | AC | 159 ms | 19892 KB |
29.txt | AC | 153 ms | 19836 KB |
30.txt | AC | 166 ms | 20608 KB |
31.txt | AC | 118 ms | 13492 KB |
32.txt | AC | 164 ms | 22100 KB |
33.txt | AC | 149 ms | 19712 KB |
34.txt | AC | 108 ms | 18816 KB |
35.txt | AC | 67 ms | 13804 KB |
36.txt | AC | 90 ms | 12840 KB |
37.txt | AC | 115 ms | 18816 KB |
38.txt | AC | 107 ms | 18688 KB |
sample_01.txt | AC | 4 ms | 7296 KB |
sample_02.txt | AC | 4 ms | 7296 KB |
sample_03.txt | AC | 4 ms | 7296 KB |
w1.txt | AC | 201 ms | 21328 KB |
w10.txt | AC | 343 ms | 41216 KB |
w11.txt | AC | 66 ms | 11136 KB |
w12.txt | AC | 96 ms | 11264 KB |
w13.txt | AC | 210 ms | 15744 KB |
w14.txt | AC | 369 ms | 23680 KB |
w15.txt | AC | 58 ms | 12056 KB |
w16.txt | AC | 81 ms | 11996 KB |
w17.txt | AC | 111 ms | 12276 KB |
w18.txt | AC | 234 ms | 14804 KB |
w2.txt | AC | 198 ms | 21272 KB |
w3.txt | AC | 308 ms | 24964 KB |
w4.txt | AC | 203 ms | 24428 KB |
w5.txt | AC | 374 ms | 44404 KB |
w6.txt | AC | 319 ms | 24824 KB |
w7.txt | AC | 338 ms | 38604 KB |
w8.txt | AC | 363 ms | 38784 KB |
w9.txt | AC | 367 ms | 39552 KB |