# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
426030 | 2021-06-13T13:06:29 Z | duality | From Hacks to Snitches (BOI21_watchmen) | C++11 | 6000 ms | 66908 KB |
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back typedef long long int LLI; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii; vi adjList[250000]; pair<int,pii> p[250000]; vi dist[250000]; int done[250000]; priority_queue<pii> H; int main() { int i,j; int N,M,K; int u,v,l; scanf("%d %d",&N,&M); for (i = 0; i < M; i++) { scanf("%d %d",&u,&v); u--,v--; adjList[u].pb(v); adjList[v].pb(u); } scanf("%d",&K); for (i = 0; i < K; i++) { scanf("%d",&l); for (j = 0; j < l; j++) scanf("%d",&v),p[v-1] = mp(l,mp(j,i)); } for (i = 0; i < N; i++) { if (p[i].first == 0) p[i].first = 1; dist[i].resize(p[i].first); fill(dist[i].begin(),dist[i].end(),-1); } dist[0][0] = 0,H.push(mp(0,0)); while (!H.empty()) { int u = H.top().second; int d = -H.top().first; H.pop(); if (d > dist[u][d % p[u].first]) continue; else if (u == N-1) { printf("%d\n",d); return 0; } for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i],t = d; for (j = 0; j < ((p[u].first == 1) ? p[v].first:1); j++) { if (done[v] && (p[u].first == 1)) break; int bad = 0; if (p[v].first != 1) { if (((d+1) % p[v].first) == p[v].second.first) bad = 1; if (((d % p[v].first) == p[v].second.first) && (p[u].second.second == p[v].second.second) \ && (p[u].second.first == ((p[v].second.first+1) % p[v].first))) bad = 1; } if (!bad) { if ((dist[v][(d+1) % p[v].first] == -1) || (d+1 < dist[v][(d+1) % p[v].first])) { dist[v][(d+1) % p[v].first] = d+1; H.push(mp(-(d+1),v)); } } d++; if ((p[u].first != 1) && ((d % p[u].first) == p[u].second.first)) break; } if ((p[u].first == 1) && (p[v].first != 1)) done[v] = 1; d = t; } } printf("impossible\n"); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 13568 KB | Output is correct |
2 | Correct | 156 ms | 19920 KB | Output is correct |
3 | Correct | 115 ms | 19560 KB | Output is correct |
4 | Correct | 205 ms | 19780 KB | Output is correct |
5 | Correct | 10 ms | 12108 KB | Output is correct |
6 | Correct | 132 ms | 19568 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 13572 KB | Output is correct |
2 | Correct | 110 ms | 19908 KB | Output is correct |
3 | Correct | 123 ms | 19460 KB | Output is correct |
4 | Correct | 147 ms | 19780 KB | Output is correct |
5 | Correct | 8 ms | 12116 KB | Output is correct |
6 | Correct | 123 ms | 19524 KB | Output is correct |
7 | Correct | 118 ms | 19168 KB | Output is correct |
8 | Correct | 140 ms | 19336 KB | Output is correct |
9 | Correct | 139 ms | 19076 KB | Output is correct |
10 | Correct | 163 ms | 19596 KB | Output is correct |
11 | Correct | 134 ms | 19328 KB | Output is correct |
12 | Correct | 120 ms | 19412 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 13572 KB | Output is correct |
2 | Correct | 110 ms | 19908 KB | Output is correct |
3 | Correct | 123 ms | 19460 KB | Output is correct |
4 | Correct | 147 ms | 19780 KB | Output is correct |
5 | Correct | 8 ms | 12116 KB | Output is correct |
6 | Correct | 123 ms | 19524 KB | Output is correct |
7 | Correct | 118 ms | 19168 KB | Output is correct |
8 | Correct | 140 ms | 19336 KB | Output is correct |
9 | Correct | 139 ms | 19076 KB | Output is correct |
10 | Correct | 163 ms | 19596 KB | Output is correct |
11 | Correct | 134 ms | 19328 KB | Output is correct |
12 | Correct | 120 ms | 19412 KB | Output is correct |
13 | Correct | 28 ms | 13380 KB | Output is correct |
14 | Correct | 153 ms | 19776 KB | Output is correct |
15 | Correct | 140 ms | 19660 KB | Output is correct |
16 | Correct | 171 ms | 19772 KB | Output is correct |
17 | Correct | 11 ms | 12108 KB | Output is correct |
18 | Correct | 118 ms | 19492 KB | Output is correct |
19 | Correct | 129 ms | 19048 KB | Output is correct |
20 | Correct | 135 ms | 19348 KB | Output is correct |
21 | Correct | 147 ms | 19096 KB | Output is correct |
22 | Correct | 130 ms | 19520 KB | Output is correct |
23 | Correct | 125 ms | 19440 KB | Output is correct |
24 | Correct | 125 ms | 19396 KB | Output is correct |
25 | Correct | 3136 ms | 62696 KB | Output is correct |
26 | Correct | 3270 ms | 66908 KB | Output is correct |
27 | Correct | 2885 ms | 63620 KB | Output is correct |
28 | Correct | 2248 ms | 66904 KB | Output is correct |
29 | Execution timed out | 6101 ms | 59260 KB | Time limit exceeded |
30 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 13572 KB | Output is correct |
2 | Correct | 110 ms | 19908 KB | Output is correct |
3 | Correct | 123 ms | 19460 KB | Output is correct |
4 | Correct | 147 ms | 19780 KB | Output is correct |
5 | Correct | 8 ms | 12116 KB | Output is correct |
6 | Correct | 123 ms | 19524 KB | Output is correct |
7 | Correct | 118 ms | 19168 KB | Output is correct |
8 | Correct | 140 ms | 19336 KB | Output is correct |
9 | Correct | 139 ms | 19076 KB | Output is correct |
10 | Correct | 163 ms | 19596 KB | Output is correct |
11 | Correct | 134 ms | 19328 KB | Output is correct |
12 | Correct | 120 ms | 19412 KB | Output is correct |
13 | Correct | 28 ms | 13380 KB | Output is correct |
14 | Correct | 153 ms | 19776 KB | Output is correct |
15 | Correct | 140 ms | 19660 KB | Output is correct |
16 | Correct | 171 ms | 19772 KB | Output is correct |
17 | Correct | 11 ms | 12108 KB | Output is correct |
18 | Correct | 118 ms | 19492 KB | Output is correct |
19 | Correct | 129 ms | 19048 KB | Output is correct |
20 | Correct | 135 ms | 19348 KB | Output is correct |
21 | Correct | 147 ms | 19096 KB | Output is correct |
22 | Correct | 130 ms | 19520 KB | Output is correct |
23 | Correct | 125 ms | 19440 KB | Output is correct |
24 | Correct | 125 ms | 19396 KB | Output is correct |
25 | Correct | 3136 ms | 62696 KB | Output is correct |
26 | Correct | 3270 ms | 66908 KB | Output is correct |
27 | Correct | 2885 ms | 63620 KB | Output is correct |
28 | Correct | 2248 ms | 66904 KB | Output is correct |
29 | Execution timed out | 6101 ms | 59260 KB | Time limit exceeded |
30 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 13568 KB | Output is correct |
2 | Correct | 156 ms | 19920 KB | Output is correct |
3 | Correct | 115 ms | 19560 KB | Output is correct |
4 | Correct | 205 ms | 19780 KB | Output is correct |
5 | Correct | 10 ms | 12108 KB | Output is correct |
6 | Correct | 132 ms | 19568 KB | Output is correct |
7 | Correct | 26 ms | 13572 KB | Output is correct |
8 | Correct | 110 ms | 19908 KB | Output is correct |
9 | Correct | 123 ms | 19460 KB | Output is correct |
10 | Correct | 147 ms | 19780 KB | Output is correct |
11 | Correct | 8 ms | 12116 KB | Output is correct |
12 | Correct | 123 ms | 19524 KB | Output is correct |
13 | Correct | 118 ms | 19168 KB | Output is correct |
14 | Correct | 140 ms | 19336 KB | Output is correct |
15 | Correct | 139 ms | 19076 KB | Output is correct |
16 | Correct | 163 ms | 19596 KB | Output is correct |
17 | Correct | 134 ms | 19328 KB | Output is correct |
18 | Correct | 120 ms | 19412 KB | Output is correct |
19 | Correct | 9 ms | 11980 KB | Output is correct |
20 | Correct | 9 ms | 11980 KB | Output is correct |
21 | Correct | 11 ms | 12048 KB | Output is correct |
22 | Correct | 37 ms | 13216 KB | Output is correct |
23 | Correct | 145 ms | 19500 KB | Output is correct |
24 | Correct | 110 ms | 19272 KB | Output is correct |
25 | Correct | 155 ms | 19556 KB | Output is correct |
26 | Correct | 8 ms | 12108 KB | Output is correct |
27 | Correct | 105 ms | 19312 KB | Output is correct |
28 | Correct | 121 ms | 18876 KB | Output is correct |
29 | Correct | 111 ms | 19120 KB | Output is correct |
30 | Correct | 115 ms | 18972 KB | Output is correct |
31 | Correct | 137 ms | 19400 KB | Output is correct |
32 | Correct | 151 ms | 19284 KB | Output is correct |
33 | Correct | 123 ms | 19272 KB | Output is correct |
34 | Correct | 3162 ms | 63356 KB | Output is correct |
35 | Correct | 3639 ms | 59816 KB | Output is correct |
36 | Correct | 3385 ms | 59856 KB | Output is correct |
37 | Incorrect | 2849 ms | 65248 KB | Output isn't correct |
38 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 13568 KB | Output is correct |
2 | Correct | 156 ms | 19920 KB | Output is correct |
3 | Correct | 115 ms | 19560 KB | Output is correct |
4 | Correct | 205 ms | 19780 KB | Output is correct |
5 | Correct | 10 ms | 12108 KB | Output is correct |
6 | Correct | 132 ms | 19568 KB | Output is correct |
7 | Correct | 26 ms | 13572 KB | Output is correct |
8 | Correct | 110 ms | 19908 KB | Output is correct |
9 | Correct | 123 ms | 19460 KB | Output is correct |
10 | Correct | 147 ms | 19780 KB | Output is correct |
11 | Correct | 8 ms | 12116 KB | Output is correct |
12 | Correct | 123 ms | 19524 KB | Output is correct |
13 | Correct | 118 ms | 19168 KB | Output is correct |
14 | Correct | 140 ms | 19336 KB | Output is correct |
15 | Correct | 139 ms | 19076 KB | Output is correct |
16 | Correct | 163 ms | 19596 KB | Output is correct |
17 | Correct | 134 ms | 19328 KB | Output is correct |
18 | Correct | 120 ms | 19412 KB | Output is correct |
19 | Correct | 28 ms | 13380 KB | Output is correct |
20 | Correct | 153 ms | 19776 KB | Output is correct |
21 | Correct | 140 ms | 19660 KB | Output is correct |
22 | Correct | 171 ms | 19772 KB | Output is correct |
23 | Correct | 11 ms | 12108 KB | Output is correct |
24 | Correct | 118 ms | 19492 KB | Output is correct |
25 | Correct | 129 ms | 19048 KB | Output is correct |
26 | Correct | 135 ms | 19348 KB | Output is correct |
27 | Correct | 147 ms | 19096 KB | Output is correct |
28 | Correct | 130 ms | 19520 KB | Output is correct |
29 | Correct | 125 ms | 19440 KB | Output is correct |
30 | Correct | 125 ms | 19396 KB | Output is correct |
31 | Correct | 3136 ms | 62696 KB | Output is correct |
32 | Correct | 3270 ms | 66908 KB | Output is correct |
33 | Correct | 2885 ms | 63620 KB | Output is correct |
34 | Correct | 2248 ms | 66904 KB | Output is correct |
35 | Execution timed out | 6101 ms | 59260 KB | Time limit exceeded |
36 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 27 ms | 13568 KB | Output is correct |
2 | Correct | 156 ms | 19920 KB | Output is correct |
3 | Correct | 115 ms | 19560 KB | Output is correct |
4 | Correct | 205 ms | 19780 KB | Output is correct |
5 | Correct | 10 ms | 12108 KB | Output is correct |
6 | Correct | 132 ms | 19568 KB | Output is correct |
7 | Correct | 26 ms | 13572 KB | Output is correct |
8 | Correct | 110 ms | 19908 KB | Output is correct |
9 | Correct | 123 ms | 19460 KB | Output is correct |
10 | Correct | 147 ms | 19780 KB | Output is correct |
11 | Correct | 8 ms | 12116 KB | Output is correct |
12 | Correct | 123 ms | 19524 KB | Output is correct |
13 | Correct | 118 ms | 19168 KB | Output is correct |
14 | Correct | 140 ms | 19336 KB | Output is correct |
15 | Correct | 139 ms | 19076 KB | Output is correct |
16 | Correct | 163 ms | 19596 KB | Output is correct |
17 | Correct | 134 ms | 19328 KB | Output is correct |
18 | Correct | 120 ms | 19412 KB | Output is correct |
19 | Correct | 28 ms | 13380 KB | Output is correct |
20 | Correct | 153 ms | 19776 KB | Output is correct |
21 | Correct | 140 ms | 19660 KB | Output is correct |
22 | Correct | 171 ms | 19772 KB | Output is correct |
23 | Correct | 11 ms | 12108 KB | Output is correct |
24 | Correct | 118 ms | 19492 KB | Output is correct |
25 | Correct | 129 ms | 19048 KB | Output is correct |
26 | Correct | 135 ms | 19348 KB | Output is correct |
27 | Correct | 147 ms | 19096 KB | Output is correct |
28 | Correct | 130 ms | 19520 KB | Output is correct |
29 | Correct | 125 ms | 19440 KB | Output is correct |
30 | Correct | 125 ms | 19396 KB | Output is correct |
31 | Correct | 3136 ms | 62696 KB | Output is correct |
32 | Correct | 3270 ms | 66908 KB | Output is correct |
33 | Correct | 2885 ms | 63620 KB | Output is correct |
34 | Correct | 2248 ms | 66904 KB | Output is correct |
35 | Execution timed out | 6101 ms | 59260 KB | Time limit exceeded |
36 | Halted | 0 ms | 0 KB | - |