Submission #880182
Source Code Expand
#include <iostream> #include <cstdio> #include <vector> #include <deque> using namespace std; const int maxn = int(1e5)+5, maxm = int(2e5)+5; int n, m; vector<pair<int, int>> graph[maxn]; int vv[maxm]; pair<pair<int, bool>, pair<int, bool>> edge[maxm]; bool vis(int x, int y) { if(edge[y].first.first == x) return edge[y].first.second; else return edge[y].second.second; } void mark(int x, int y) { if(edge[y].first.first == x) edge[y].first.second = 1; else edge[y].second.second = 1; } int bfs() { deque<pair<int, pair<int, int>>> Q; for(auto it: graph[1]) { Q.push_back({it.first, {it.second, 1}}); } pair<int, pair<int, int>> top; while(!Q.empty()) { top = Q.front(); Q.pop_front(); if(vis(top.first, top.second.first)) continue; mark(top.first, top.second.first); if(top.first == n) return top.second.second; for(auto it: graph[top.first]) { if(!vis(it.first, it.second)) { if(vv[top.second.first] == vv[it.second]) Q.push_front({it.first, {it.second, top.second.second}}); else Q.push_back({it.first, {it.second, top.second.second+1}}); } } } return -1; } int main(void) { int u, v, c; scanf("%d%d", &n, &m); for(int i = 0;i < m;i++) { scanf("%d%d%d", &u, &v, &c); graph[u].push_back({v, i}); graph[v].push_back({u, i}); vv[i] = c; edge[i] = {{u, 0}, {v, 0}}; } printf("%d\n", bfs()); }
Submission Info
Submission Time | |
---|---|
Task | E - Snuke's Subway Trip |
User | NibNalin |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1433 Byte |
Status | MLE |
Exec Time | 3313 ms |
Memory | 1522516 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:57:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d", &n, &m); ^ ./Main.cpp:61:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d%d", &u, &v, &c); ^
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, 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 | 8 ms | 2560 KB |
02.txt | AC | 160 ms | 21648 KB |
03.txt | AC | 209 ms | 16256 KB |
04.txt | AC | 155 ms | 12672 KB |
05.txt | AC | 219 ms | 16896 KB |
06.txt | AC | 81 ms | 7680 KB |
07.txt | AC | 94 ms | 8704 KB |
08.txt | AC | 199 ms | 14720 KB |
09.txt | AC | 94 ms | 8832 KB |
10.txt | AC | 98 ms | 8832 KB |
11.txt | TLE | 3277 ms | 1084180 KB |
12.txt | AC | 270 ms | 63928 KB |
13.txt | TLE | 3284 ms | 1153116 KB |
14.txt | MLE | 2439 ms | 680684 KB |
15.txt | TLE | 3309 ms | 1451344 KB |
16.txt | TLE | 3277 ms | 1110716 KB |
17.txt | TLE | 3272 ms | 1115632 KB |
18.txt | TLE | 3274 ms | 1135196 KB |
19.txt | TLE | 3278 ms | 1153928 KB |
20.txt | TLE | 3279 ms | 1122804 KB |
21.txt | MLE | 981 ms | 257944 KB |
22.txt | TLE | 3276 ms | 1124068 KB |
23.txt | AC | 339 ms | 53772 KB |
24.txt | TLE | 3313 ms | 1503620 KB |
25.txt | AC | 308 ms | 90628 KB |
26.txt | TLE | 3309 ms | 1498892 KB |
27.txt | AC | 232 ms | 35900 KB |
28.txt | TLE | 3299 ms | 1397668 KB |
29.txt | TLE | 3225 ms | 617604 KB |
30.txt | TLE | 3302 ms | 1468436 KB |
31.txt | TLE | 3299 ms | 1454584 KB |
32.txt | TLE | 3297 ms | 1421800 KB |
33.txt | AC | 2639 ms | 166028 KB |
34.txt | TLE | 3267 ms | 1076036 KB |
35.txt | AC | 309 ms | 85532 KB |
36.txt | TLE | 3266 ms | 1095468 KB |
37.txt | MLE | 1223 ms | 346516 KB |
38.txt | TLE | 3269 ms | 1099728 KB |
sample_01.txt | AC | 8 ms | 2560 KB |
sample_02.txt | AC | 8 ms | 2560 KB |
sample_03.txt | AC | 8 ms | 2560 KB |
w1.txt | TLE | 3267 ms | 1076008 KB |
w10.txt | AC | 186 ms | 11904 KB |
w11.txt | AC | 494 ms | 110328 KB |
w12.txt | AC | 488 ms | 104740 KB |
w13.txt | AC | 2036 ms | 16740 KB |
w14.txt | AC | 255 ms | 11904 KB |
w15.txt | AC | 564 ms | 120520 KB |
w16.txt | TLE | 3235 ms | 745764 KB |
w17.txt | AC | 1064 ms | 221592 KB |
w18.txt | AC | 374 ms | 12032 KB |
w2.txt | TLE | 3270 ms | 1120420 KB |
w3.txt | TLE | 3275 ms | 1164312 KB |
w4.txt | TLE | 3307 ms | 1522516 KB |
w5.txt | TLE | 3270 ms | 1112528 KB |
w6.txt | TLE | 3269 ms | 1117168 KB |
w7.txt | TLE | 3250 ms | 935972 KB |
w8.txt | TLE | 3166 ms | 82224 KB |
w9.txt | AC | 1423 ms | 11432 KB |