Submission #3591158
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]; } 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; for (auto kv : C) { int i = kv.first; UnionFind uf(N); REP(j, C[i].size()) { auto p = C[i][j]; uf.unite(p.first, p.second); } map<int, int> id; set<pair<int, 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({id[pp], p.first}) == 0) { G[id[pp]].push_back(p.first); G[p.first].push_back(id[pp]); } if (used.count({id[pp], p.second}) == 0) { G[id[pp]].push_back(p.second); G[p.second].push_back(id[pp]); } used.insert({id[pp], p.first}); used.insert({id[pp], 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 | 0 |
Code Size | 3514 Byte |
Status | TLE |
Exec Time | 3157 ms |
Memory | 39552 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 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 | 138 ms | 13184 KB |
03.txt | TLE | 3157 ms | 31032 KB |
04.txt | AC | 470 ms | 29296 KB |
05.txt | AC | 449 ms | 28124 KB |
06.txt | AC | 219 ms | 21464 KB |
07.txt | AC | 266 ms | 23488 KB |
08.txt | TLE | 3157 ms | 31184 KB |
09.txt | AC | 318 ms | 21244 KB |
10.txt | AC | 256 ms | 20560 KB |
11.txt | AC | 184 ms | 21560 KB |
12.txt | AC | 78 ms | 12260 KB |
13.txt | AC | 142 ms | 15180 KB |
14.txt | AC | 182 ms | 21952 KB |
15.txt | AC | 176 ms | 25068 KB |
16.txt | AC | 177 ms | 23112 KB |
17.txt | AC | 180 ms | 21144 KB |
18.txt | AC | 118 ms | 13476 KB |
19.txt | AC | 180 ms | 23148 KB |
20.txt | AC | 175 ms | 20156 KB |
21.txt | TLE | 3156 ms | 24644 KB |
22.txt | AC | 260 ms | 19660 KB |
23.txt | AC | 300 ms | 23564 KB |
24.txt | AC | 175 ms | 20544 KB |
25.txt | AC | 77 ms | 11380 KB |
26.txt | AC | 138 ms | 15332 KB |
27.txt | AC | 185 ms | 18256 KB |
28.txt | AC | 173 ms | 20100 KB |
29.txt | AC | 173 ms | 18764 KB |
30.txt | AC | 186 ms | 21172 KB |
31.txt | AC | 129 ms | 13620 KB |
32.txt | AC | 179 ms | 23124 KB |
33.txt | AC | 171 ms | 18640 KB |
34.txt | AC | 166 ms | 16816 KB |
35.txt | AC | 76 ms | 13676 KB |
36.txt | AC | 98 ms | 12712 KB |
37.txt | AC | 178 ms | 16700 KB |
38.txt | AC | 167 ms | 16792 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 | 847 ms | 23120 KB |
w10.txt | TLE | 3157 ms | 30368 KB |
w11.txt | AC | 71 ms | 11136 KB |
w12.txt | AC | 102 ms | 11264 KB |
w13.txt | AC | 248 ms | 15744 KB |
w14.txt | AC | 377 ms | 23712 KB |
w15.txt | AC | 64 ms | 12056 KB |
w16.txt | AC | 86 ms | 11996 KB |
w17.txt | AC | 122 ms | 11636 KB |
w18.txt | AC | 285 ms | 15828 KB |
w2.txt | AC | 335 ms | 23064 KB |
w3.txt | AC | 304 ms | 26972 KB |
w4.txt | AC | 211 ms | 26092 KB |
w5.txt | TLE | 3157 ms | 31056 KB |
w6.txt | AC | 319 ms | 24392 KB |
w7.txt | AC | 350 ms | 38608 KB |
w8.txt | AC | 476 ms | 38912 KB |
w9.txt | AC | 1557 ms | 39552 KB |