Submission #3591131
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]; vector<vector<pair<int, int>>> C(1000005); signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, M; cin >> N >> M; REP(i, M) { int p, q, c; cin >> p >> q >> c; p--; q--; c--; C[c].push_back({p, q}); } int sz = N; REP(i, C.size()) { 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 | 3489 Byte |
Status | TLE |
Exec Time | 3157 ms |
Memory | 50360 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 | 132 ms | 30720 KB |
02.txt | AC | 2309 ms | 36608 KB |
03.txt | TLE | 3156 ms | 39232 KB |
04.txt | TLE | 3157 ms | 49660 KB |
05.txt | TLE | 3157 ms | 50360 KB |
06.txt | TLE | 3156 ms | 44800 KB |
07.txt | TLE | 3156 ms | 48172 KB |
08.txt | TLE | 3156 ms | 41228 KB |
09.txt | TLE | 3156 ms | 44668 KB |
10.txt | TLE | 3156 ms | 44240 KB |
11.txt | TLE | 3156 ms | 45012 KB |
12.txt | AC | 1101 ms | 34028 KB |
13.txt | TLE | 3156 ms | 37628 KB |
14.txt | TLE | 3156 ms | 45936 KB |
15.txt | TLE | 3157 ms | 47340 KB |
16.txt | TLE | 3157 ms | 45028 KB |
17.txt | TLE | 3156 ms | 46316 KB |
18.txt | TLE | 3156 ms | 37316 KB |
19.txt | TLE | 3156 ms | 46276 KB |
20.txt | TLE | 3157 ms | 43884 KB |
21.txt | TLE | 3156 ms | 39056 KB |
22.txt | TLE | 3156 ms | 42452 KB |
23.txt | TLE | 3157 ms | 46116 KB |
24.txt | TLE | 3156 ms | 42928 KB |
25.txt | AC | 1080 ms | 34804 KB |
26.txt | TLE | 3156 ms | 37620 KB |
27.txt | TLE | 3156 ms | 41680 KB |
28.txt | TLE | 3156 ms | 43720 KB |
29.txt | TLE | 3156 ms | 44108 KB |
30.txt | TLE | 3156 ms | 47120 KB |
31.txt | TLE | 3156 ms | 36728 KB |
32.txt | TLE | 3157 ms | 45000 KB |
33.txt | TLE | 3156 ms | 41936 KB |
34.txt | TLE | 3156 ms | 39964 KB |
35.txt | AC | 1093 ms | 36848 KB |
36.txt | TLE | 3156 ms | 35620 KB |
37.txt | TLE | 3156 ms | 40184 KB |
38.txt | TLE | 3156 ms | 42236 KB |
sample_01.txt | AC | 112 ms | 30720 KB |
sample_02.txt | AC | 126 ms | 30720 KB |
sample_03.txt | AC | 110 ms | 30720 KB |
w1.txt | TLE | 3156 ms | 46288 KB |
w10.txt | TLE | 3156 ms | 37728 KB |
w11.txt | AC | 258 ms | 34560 KB |
w12.txt | AC | 722 ms | 34688 KB |
w13.txt | TLE | 3156 ms | 38784 KB |
w14.txt | TLE | 3157 ms | 45600 KB |
w15.txt | AC | 261 ms | 33960 KB |
w16.txt | AC | 724 ms | 34028 KB |
w17.txt | TLE | 3156 ms | 34268 KB |
w18.txt | TLE | 3156 ms | 40056 KB |
w2.txt | TLE | 3156 ms | 46192 KB |
w3.txt | TLE | 3156 ms | 50316 KB |
w4.txt | TLE | 3157 ms | 48876 KB |
w5.txt | TLE | 3156 ms | 39232 KB |
w6.txt | TLE | 3157 ms | 46464 KB |
w7.txt | AC | 347 ms | 47824 KB |
w8.txt | AC | 792 ms | 48128 KB |
w9.txt | TLE | 3156 ms | 41600 KB |