oj.uz

Submission #426412

# Submission time Handle Problem Language Result Execution time Memory
426412 2021-06-14T01:39:20 Z duality From Hacks to Snitches (BOI21_watchmen) C++11
80 / 100
 6000 ms 299692 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],adjList2[250000];
pair<int,pii> p[250000];
bool comp(int a,int b) {
    return p[a] < p[b];
}
int pos[250000];
vector<LLI> dist[250000];
priority_queue<pair<LLI,int> > H;
int relax(int u,LLI d) {
    if ((dist[u][d % p[u].first] == -1) || (d < dist[u][d % p[u].first])) {
        dist[u][d % p[u].first] = d;
        H.push(mp(-d,u));
    }
    return 0;
}
int done[250000],done2[250000];
set<pii> done3[250000];
int gcd(int a,int b) {
    int t;
    while (a > 0) t = b % a,b = a,a = t;
    return b;
}
int poss[3000][3000];
int ggcd[3000][3000];
int inv[3000][3000];
vi ll;
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),ll.pb(l);
        for (j = 0; j < l; j++) scanf("%d",&v),p[v-1] = mp(l,mp(j,i));
    }

    int k;
    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);
    }
    for (i = 0; i < N; i++) {
        sort(adjList[i].begin(),adjList[i].end(),comp);
        while ((pos[i] < adjList[i].size()) && (p[adjList[i][pos[i]]].first == 1)) pos[i]++;
        for (j = 0; j < adjList[i].size(); j++) {
            int v = adjList[i][j];
            if ((p[i].first > 1) && (p[v].first > 1) && (p[i].second.second != p[v].second.second)) adjList2[i].pb(v);
        }
    }
    for (i = 0; i < ll.size(); i++) {
        for (j = 0; j < ll.size(); j++) {
            int g = gcd(ll[i],ll[j]);
            poss[ll[i]/g][(ll[j] % ll[i])/g] = 1;
        }
    }
    for (i = 1; i < 3000; i++) {
        for (j = 0; j <= i; j++) {
            ggcd[i][j] = gcd(i,j);
            if (ggcd[i][j] == 1) {
                if (poss[i][j]) {
                    for (k = 1; k < i; k++) {
                        if (((j*k) % i) == 1) break;
                    }
                    inv[i][j] = k;
                }
            }
        }
    }
    dist[0][0] = 0,H.push(mp(0,0));
    while (!H.empty()) {
        int u = H.top().second;
        LLI d = -H.top().first;
        H.pop();

        if (d > dist[u][d % p[u].first]) continue;
        else if (u == N-1) {
            printf("%lld\n",d);
            return 0;
        }
        if ((p[u].first == 1) || (((d+1) % p[u].first) != p[u].second.first)) relax(u,d+1);
        if (done[u] && (dist[u][(d+p[u].first-1) % p[u].first] == d-1)) {
            for (i = 0; i < adjList2[u].size(); i++) {
                int v = adjList2[u][i];
                if (done3[v].count(mp(d % p[v].first,p[u].first))) continue;
                int a = p[u].first,b = p[v].second.first-d,c = p[v].first;
                b = ((b % c)+c) % c,a %= c;
                int g = gcd(a,c);
                if ((b % g) == 0) {
                    j = (inv[c/g][a/g]*(b/g)) % (c/g);
                    LLI d2 = d+(LLI) j*p[u].first+1;
                    assert((d2 % p[v].first) == ((p[v].second.first+1) % p[v].first));
                    if ((d2 % p[v].first) != p[v].second.first) relax(v,d2);
                }
                done3[v].insert(mp(d % p[v].first,p[u].first));
            }
            continue;
        }
        for (i = done[u] ? pos[u]:0; i < adjList[u].size(); i++) {
            int v = adjList[u][i];
            if (p[v].first == 1) relax(v,d+1);
            else if (p[u].first == 1) {
                if (done2[v]) continue;
                else {
                    for (j = 0; j < p[v].first; j++) {
                        LLI d2 = d+j+1;
                        if ((d2 % p[v].first) != p[v].second.first) relax(v,d2);
                    }
                    done2[v] = 1;
                }
            }
            else if (p[u].second.second == p[v].second.second) {
                if (((d+1) % p[v].first) == p[v].second.first) continue;
                if (((d % p[v].first) == p[v].second.first) && (((d+1) % p[u].first) == p[u].second.first)) continue;
                relax(v,d+1);
            }
            else {
                if (done3[v].count(mp(d % p[v].first,p[u].first))) continue;
                for (j = 0; j < p[v].first; j++) {
                    LLI d2 = d+(LLI) j*p[u].first+1;
                    if ((d2 % p[v].first) != p[v].second.first) relax(v,d2);
                }
                done3[v].insert(mp(d % p[v].first,p[u].first));
            }
        }
        done[u] = 1;
    }
    printf("impossible\n");

    return 0;
}

Compilation message

watchmen.cpp: In function 'int main()':
watchmen.cpp:61:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         while ((pos[i] < adjList[i].size()) && (p[adjList[i][pos[i]]].first == 1)) pos[i]++;
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (j = 0; j < adjList[i].size(); j++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (i = 0; i < ll.size(); i++) {
      |                 ~~^~~~~~~~~~~
watchmen.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (j = 0; j < ll.size(); j++) {
      |                     ~~^~~~~~~~~~~
watchmen.cpp:99:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |             for (i = 0; i < adjList2[u].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
watchmen.cpp:115:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |         for (i = done[u] ? pos[u]:0; i < adjList[u].size(); i++) {
      |                                      ~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
watchmen.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
watchmen.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d",&K);
      |     ~~~~~^~~~~~~~~
watchmen.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d",&l),ll.pb(l);
      |         ~~~~~^~~~~~~~~
watchmen.cpp:50:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         for (j = 0; j < l; j++) scanf("%d",&v),p[v-1] = mp(l,mp(j,i));
      |                                 ~~~~~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 59052 KB Output is correct
2 Correct 360 ms 65992 KB Output is correct
3 Correct 369 ms 65480 KB Output is correct
4 Correct 366 ms 65844 KB Output is correct
5 Correct 256 ms 57408 KB Output is correct
6 Correct 374 ms 65388 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 59076 KB Output is correct
2 Correct 366 ms 66000 KB Output is correct
3 Correct 375 ms 65616 KB Output is correct
4 Correct 353 ms 65736 KB Output is correct
5 Correct 260 ms 57396 KB Output is correct
6 Correct 355 ms 65416 KB Output is correct
7 Correct 371 ms 64984 KB Output is correct
8 Correct 360 ms 65272 KB Output is correct
9 Correct 359 ms 65036 KB Output is correct
10 Correct 387 ms 65472 KB Output is correct
11 Correct 374 ms 65296 KB Output is correct
12 Correct 375 ms 65296 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 59076 KB Output is correct
2 Correct 366 ms 66000 KB Output is correct
3 Correct 375 ms 65616 KB Output is correct
4 Correct 353 ms 65736 KB Output is correct
5 Correct 260 ms 57396 KB Output is correct
6 Correct 355 ms 65416 KB Output is correct
7 Correct 371 ms 64984 KB Output is correct
8 Correct 360 ms 65272 KB Output is correct
9 Correct 359 ms 65036 KB Output is correct
10 Correct 387 ms 65472 KB Output is correct
11 Correct 374 ms 65296 KB Output is correct
12 Correct 375 ms 65296 KB Output is correct
13 Correct 284 ms 58620 KB Output is correct
14 Correct 396 ms 65812 KB Output is correct
15 Correct 361 ms 65480 KB Output is correct
16 Correct 387 ms 65828 KB Output is correct
17 Correct 251 ms 57432 KB Output is correct
18 Correct 354 ms 65352 KB Output is correct
19 Correct 404 ms 65020 KB Output is correct
20 Correct 376 ms 65288 KB Output is correct
21 Correct 345 ms 65012 KB Output is correct
22 Correct 347 ms 65460 KB Output is correct
23 Correct 374 ms 65348 KB Output is correct
24 Correct 383 ms 65228 KB Output is correct
25 Correct 3268 ms 110652 KB Output is correct
26 Correct 3243 ms 114884 KB Output is correct
27 Correct 2976 ms 111500 KB Output is correct
28 Correct 2288 ms 114480 KB Output is correct
29 Correct 2965 ms 107860 KB Output is correct
30 Correct 3376 ms 110776 KB Output is correct
31 Correct 3462 ms 115556 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 59076 KB Output is correct
2 Correct 366 ms 66000 KB Output is correct
3 Correct 375 ms 65616 KB Output is correct
4 Correct 353 ms 65736 KB Output is correct
5 Correct 260 ms 57396 KB Output is correct
6 Correct 355 ms 65416 KB Output is correct
7 Correct 371 ms 64984 KB Output is correct
8 Correct 360 ms 65272 KB Output is correct
9 Correct 359 ms 65036 KB Output is correct
10 Correct 387 ms 65472 KB Output is correct
11 Correct 374 ms 65296 KB Output is correct
12 Correct 375 ms 65296 KB Output is correct
13 Correct 284 ms 58620 KB Output is correct
14 Correct 396 ms 65812 KB Output is correct
15 Correct 361 ms 65480 KB Output is correct
16 Correct 387 ms 65828 KB Output is correct
17 Correct 251 ms 57432 KB Output is correct
18 Correct 354 ms 65352 KB Output is correct
19 Correct 404 ms 65020 KB Output is correct
20 Correct 376 ms 65288 KB Output is correct
21 Correct 345 ms 65012 KB Output is correct
22 Correct 347 ms 65460 KB Output is correct
23 Correct 374 ms 65348 KB Output is correct
24 Correct 383 ms 65228 KB Output is correct
25 Correct 3268 ms 110652 KB Output is correct
26 Correct 3243 ms 114884 KB Output is correct
27 Correct 2976 ms 111500 KB Output is correct
28 Correct 2288 ms 114480 KB Output is correct
29 Correct 2965 ms 107860 KB Output is correct
30 Correct 3376 ms 110776 KB Output is correct
31 Correct 3462 ms 115556 KB Output is correct
32 Correct 294 ms 58620 KB Output is correct
33 Correct 392 ms 65660 KB Output is correct
34 Correct 368 ms 65480 KB Output is correct
35 Correct 358 ms 65736 KB Output is correct
36 Correct 274 ms 57420 KB Output is correct
37 Correct 371 ms 65452 KB Output is correct
38 Correct 359 ms 64956 KB Output is correct
39 Correct 375 ms 65396 KB Output is correct
40 Correct 365 ms 64968 KB Output is correct
41 Correct 390 ms 65392 KB Output is correct
42 Correct 354 ms 65236 KB Output is correct
43 Correct 359 ms 65344 KB Output is correct
44 Correct 3367 ms 110572 KB Output is correct
45 Correct 2986 ms 114880 KB Output is correct
46 Correct 3119 ms 111520 KB Output is correct
47 Correct 2383 ms 114548 KB Output is correct
48 Correct 2894 ms 107852 KB Output is correct
49 Correct 2946 ms 110636 KB Output is correct
50 Correct 3413 ms 115624 KB Output is correct
51 Correct 3541 ms 127900 KB Output is correct
52 Correct 3854 ms 144328 KB Output is correct
53 Correct 3941 ms 145948 KB Output is correct
54 Correct 2135 ms 107004 KB Output is correct
55 Correct 4032 ms 192724 KB Output is correct
56 Correct 3698 ms 150280 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 59052 KB Output is correct
2 Correct 360 ms 65992 KB Output is correct
3 Correct 369 ms 65480 KB Output is correct
4 Correct 366 ms 65844 KB Output is correct
5 Correct 256 ms 57408 KB Output is correct
6 Correct 374 ms 65388 KB Output is correct
7 Correct 297 ms 59076 KB Output is correct
8 Correct 366 ms 66000 KB Output is correct
9 Correct 375 ms 65616 KB Output is correct
10 Correct 353 ms 65736 KB Output is correct
11 Correct 260 ms 57396 KB Output is correct
12 Correct 355 ms 65416 KB Output is correct
13 Correct 371 ms 64984 KB Output is correct
14 Correct 360 ms 65272 KB Output is correct
15 Correct 359 ms 65036 KB Output is correct
16 Correct 387 ms 65472 KB Output is correct
17 Correct 374 ms 65296 KB Output is correct
18 Correct 375 ms 65296 KB Output is correct
19 Correct 250 ms 57272 KB Output is correct
20 Correct 255 ms 57248 KB Output is correct
21 Correct 255 ms 57296 KB Output is correct
22 Correct 283 ms 58584 KB Output is correct
23 Correct 400 ms 65724 KB Output is correct
24 Correct 374 ms 65396 KB Output is correct
25 Correct 377 ms 65924 KB Output is correct
26 Correct 259 ms 57340 KB Output is correct
27 Correct 365 ms 65372 KB Output is correct
28 Correct 355 ms 64932 KB Output is correct
29 Correct 346 ms 65212 KB Output is correct
30 Correct 351 ms 64996 KB Output is correct
31 Correct 399 ms 65464 KB Output is correct
32 Correct 371 ms 65356 KB Output is correct
33 Correct 353 ms 65284 KB Output is correct
34 Correct 3588 ms 111640 KB Output is correct
35 Correct 3500 ms 108196 KB Output is correct
36 Correct 3282 ms 108220 KB Output is correct
37 Correct 3082 ms 112640 KB Output is correct
38 Correct 3041 ms 110420 KB Output is correct
39 Correct 2942 ms 112404 KB Output is correct
40 Correct 2966 ms 112872 KB Output is correct
41 Correct 3026 ms 111832 KB Output is correct
42 Correct 3052 ms 114508 KB Output is correct
43 Correct 3483 ms 118572 KB Output is correct
44 Correct 3155 ms 118848 KB Output is correct
45 Correct 3287 ms 114436 KB Output is correct
46 Correct 3100 ms 119052 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 59052 KB Output is correct
2 Correct 360 ms 65992 KB Output is correct
3 Correct 369 ms 65480 KB Output is correct
4 Correct 366 ms 65844 KB Output is correct
5 Correct 256 ms 57408 KB Output is correct
6 Correct 374 ms 65388 KB Output is correct
7 Correct 297 ms 59076 KB Output is correct
8 Correct 366 ms 66000 KB Output is correct
9 Correct 375 ms 65616 KB Output is correct
10 Correct 353 ms 65736 KB Output is correct
11 Correct 260 ms 57396 KB Output is correct
12 Correct 355 ms 65416 KB Output is correct
13 Correct 371 ms 64984 KB Output is correct
14 Correct 360 ms 65272 KB Output is correct
15 Correct 359 ms 65036 KB Output is correct
16 Correct 387 ms 65472 KB Output is correct
17 Correct 374 ms 65296 KB Output is correct
18 Correct 375 ms 65296 KB Output is correct
19 Correct 284 ms 58620 KB Output is correct
20 Correct 396 ms 65812 KB Output is correct
21 Correct 361 ms 65480 KB Output is correct
22 Correct 387 ms 65828 KB Output is correct
23 Correct 251 ms 57432 KB Output is correct
24 Correct 354 ms 65352 KB Output is correct
25 Correct 404 ms 65020 KB Output is correct
26 Correct 376 ms 65288 KB Output is correct
27 Correct 345 ms 65012 KB Output is correct
28 Correct 347 ms 65460 KB Output is correct
29 Correct 374 ms 65348 KB Output is correct
30 Correct 383 ms 65228 KB Output is correct
31 Correct 3268 ms 110652 KB Output is correct
32 Correct 3243 ms 114884 KB Output is correct
33 Correct 2976 ms 111500 KB Output is correct
34 Correct 2288 ms 114480 KB Output is correct
35 Correct 2965 ms 107860 KB Output is correct
36 Correct 3376 ms 110776 KB Output is correct
37 Correct 3462 ms 115556 KB Output is correct
38 Correct 250 ms 57272 KB Output is correct
39 Correct 255 ms 57248 KB Output is correct
40 Correct 255 ms 57296 KB Output is correct
41 Correct 283 ms 58584 KB Output is correct
42 Correct 400 ms 65724 KB Output is correct
43 Correct 374 ms 65396 KB Output is correct
44 Correct 377 ms 65924 KB Output is correct
45 Correct 259 ms 57340 KB Output is correct
46 Correct 365 ms 65372 KB Output is correct
47 Correct 355 ms 64932 KB Output is correct
48 Correct 346 ms 65212 KB Output is correct
49 Correct 351 ms 64996 KB Output is correct
50 Correct 399 ms 65464 KB Output is correct
51 Correct 371 ms 65356 KB Output is correct
52 Correct 353 ms 65284 KB Output is correct
53 Correct 3588 ms 111640 KB Output is correct
54 Correct 3500 ms 108196 KB Output is correct
55 Correct 3282 ms 108220 KB Output is correct
56 Correct 3082 ms 112640 KB Output is correct
57 Correct 3041 ms 110420 KB Output is correct
58 Correct 2942 ms 112404 KB Output is correct
59 Correct 2966 ms 112872 KB Output is correct
60 Correct 3026 ms 111832 KB Output is correct
61 Correct 3052 ms 114508 KB Output is correct
62 Correct 3483 ms 118572 KB Output is correct
63 Correct 3155 ms 118848 KB Output is correct
64 Correct 3287 ms 114436 KB Output is correct
65 Correct 3100 ms 119052 KB Output is correct
66 Correct 269 ms 57200 KB Output is correct
67 Correct 262 ms 57256 KB Output is correct
68 Correct 249 ms 57256 KB Output is correct
69 Correct 278 ms 59156 KB Output is correct
70 Correct 388 ms 66792 KB Output is correct
71 Correct 363 ms 66632 KB Output is correct
72 Correct 401 ms 66968 KB Output is correct
73 Correct 255 ms 57388 KB Output is correct
74 Correct 361 ms 66536 KB Output is correct
75 Correct 363 ms 66080 KB Output is correct
76 Correct 358 ms 66428 KB Output is correct
77 Correct 353 ms 66132 KB Output is correct
78 Correct 351 ms 66612 KB Output is correct
79 Correct 374 ms 66468 KB Output is correct
80 Correct 349 ms 66352 KB Output is correct
81 Correct 3152 ms 119684 KB Output is correct
82 Correct 3125 ms 123716 KB Output is correct
83 Correct 2969 ms 120520 KB Output is correct
84 Correct 2186 ms 123472 KB Output is correct
85 Correct 3143 ms 121512 KB Output is correct
86 Correct 3034 ms 118884 KB Output is correct
87 Correct 3258 ms 125524 KB Output is correct
88 Correct 3305 ms 121640 KB Output is correct
89 Correct 3427 ms 119104 KB Output is correct
90 Correct 3434 ms 127064 KB Output is correct
91 Correct 3299 ms 132560 KB Output is correct
92 Correct 3140 ms 114492 KB Output is correct
93 Correct 3053 ms 120600 KB Output is correct
94 Correct 3297 ms 125040 KB Output is correct
95 Correct 3170 ms 123272 KB Output is correct
96 Correct 3386 ms 125516 KB Output is correct
97 Correct 3573 ms 128704 KB Output is correct
98 Correct 3647 ms 127260 KB Output is correct
99 Correct 3740 ms 121108 KB Output is correct
100 Correct 3167 ms 119572 KB Output is correct
101 Correct 3355 ms 120000 KB Output is correct
102 Correct 3023 ms 120328 KB Output is correct
103 Correct 3122 ms 116980 KB Output is correct
104 Correct 3186 ms 119160 KB Output is correct
105 Correct 3291 ms 112892 KB Output is correct
106 Correct 3214 ms 111368 KB Output is correct
107 Correct 3211 ms 111504 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 59052 KB Output is correct
2 Correct 360 ms 65992 KB Output is correct
3 Correct 369 ms 65480 KB Output is correct
4 Correct 366 ms 65844 KB Output is correct
5 Correct 256 ms 57408 KB Output is correct
6 Correct 374 ms 65388 KB Output is correct
7 Correct 297 ms 59076 KB Output is correct
8 Correct 366 ms 66000 KB Output is correct
9 Correct 375 ms 65616 KB Output is correct
10 Correct 353 ms 65736 KB Output is correct
11 Correct 260 ms 57396 KB Output is correct
12 Correct 355 ms 65416 KB Output is correct
13 Correct 371 ms 64984 KB Output is correct
14 Correct 360 ms 65272 KB Output is correct
15 Correct 359 ms 65036 KB Output is correct
16 Correct 387 ms 65472 KB Output is correct
17 Correct 374 ms 65296 KB Output is correct
18 Correct 375 ms 65296 KB Output is correct
19 Correct 284 ms 58620 KB Output is correct
20 Correct 396 ms 65812 KB Output is correct
21 Correct 361 ms 65480 KB Output is correct
22 Correct 387 ms 65828 KB Output is correct
23 Correct 251 ms 57432 KB Output is correct
24 Correct 354 ms 65352 KB Output is correct
25 Correct 404 ms 65020 KB Output is correct
26 Correct 376 ms 65288 KB Output is correct
27 Correct 345 ms 65012 KB Output is correct
28 Correct 347 ms 65460 KB Output is correct
29 Correct 374 ms 65348 KB Output is correct
30 Correct 383 ms 65228 KB Output is correct
31 Correct 3268 ms 110652 KB Output is correct
32 Correct 3243 ms 114884 KB Output is correct
33 Correct 2976 ms 111500 KB Output is correct
34 Correct 2288 ms 114480 KB Output is correct
35 Correct 2965 ms 107860 KB Output is correct
36 Correct 3376 ms 110776 KB Output is correct
37 Correct 3462 ms 115556 KB Output is correct
38 Correct 294 ms 58620 KB Output is correct
39 Correct 392 ms 65660 KB Output is correct
40 Correct 368 ms 65480 KB Output is correct
41 Correct 358 ms 65736 KB Output is correct
42 Correct 274 ms 57420 KB Output is correct
43 Correct 371 ms 65452 KB Output is correct
44 Correct 359 ms 64956 KB Output is correct
45 Correct 375 ms 65396 KB Output is correct
46 Correct 365 ms 64968 KB Output is correct
47 Correct 390 ms 65392 KB Output is correct
48 Correct 354 ms 65236 KB Output is correct
49 Correct 359 ms 65344 KB Output is correct
50 Correct 3367 ms 110572 KB Output is correct
51 Correct 2986 ms 114880 KB Output is correct
52 Correct 3119 ms 111520 KB Output is correct
53 Correct 2383 ms 114548 KB Output is correct
54 Correct 2894 ms 107852 KB Output is correct
55 Correct 2946 ms 110636 KB Output is correct
56 Correct 3413 ms 115624 KB Output is correct
57 Correct 3541 ms 127900 KB Output is correct
58 Correct 3854 ms 144328 KB Output is correct
59 Correct 3941 ms 145948 KB Output is correct
60 Correct 2135 ms 107004 KB Output is correct
61 Correct 4032 ms 192724 KB Output is correct
62 Correct 3698 ms 150280 KB Output is correct
63 Correct 250 ms 57272 KB Output is correct
64 Correct 255 ms 57248 KB Output is correct
65 Correct 255 ms 57296 KB Output is correct
66 Correct 283 ms 58584 KB Output is correct
67 Correct 400 ms 65724 KB Output is correct
68 Correct 374 ms 65396 KB Output is correct
69 Correct 377 ms 65924 KB Output is correct
70 Correct 259 ms 57340 KB Output is correct
71 Correct 365 ms 65372 KB Output is correct
72 Correct 355 ms 64932 KB Output is correct
73 Correct 346 ms 65212 KB Output is correct
74 Correct 351 ms 64996 KB Output is correct
75 Correct 399 ms 65464 KB Output is correct
76 Correct 371 ms 65356 KB Output is correct
77 Correct 353 ms 65284 KB Output is correct
78 Correct 3588 ms 111640 KB Output is correct
79 Correct 3500 ms 108196 KB Output is correct
80 Correct 3282 ms 108220 KB Output is correct
81 Correct 3082 ms 112640 KB Output is correct
82 Correct 3041 ms 110420 KB Output is correct
83 Correct 2942 ms 112404 KB Output is correct
84 Correct 2966 ms 112872 KB Output is correct
85 Correct 3026 ms 111832 KB Output is correct
86 Correct 3052 ms 114508 KB Output is correct
87 Correct 3483 ms 118572 KB Output is correct
88 Correct 3155 ms 118848 KB Output is correct
89 Correct 3287 ms 114436 KB Output is correct
90 Correct 3100 ms 119052 KB Output is correct
91 Correct 269 ms 57200 KB Output is correct
92 Correct 262 ms 57256 KB Output is correct
93 Correct 249 ms 57256 KB Output is correct
94 Correct 278 ms 59156 KB Output is correct
95 Correct 388 ms 66792 KB Output is correct
96 Correct 363 ms 66632 KB Output is correct
97 Correct 401 ms 66968 KB Output is correct
98 Correct 255 ms 57388 KB Output is correct
99 Correct 361 ms 66536 KB Output is correct
100 Correct 363 ms 66080 KB Output is correct
101 Correct 358 ms 66428 KB Output is correct
102 Correct 353 ms 66132 KB Output is correct
103 Correct 351 ms 66612 KB Output is correct
104 Correct 374 ms 66468 KB Output is correct
105 Correct 349 ms 66352 KB Output is correct
106 Correct 3152 ms 119684 KB Output is correct
107 Correct 3125 ms 123716 KB Output is correct
108 Correct 2969 ms 120520 KB Output is correct
109 Correct 2186 ms 123472 KB Output is correct
110 Correct 3143 ms 121512 KB Output is correct
111 Correct 3034 ms 118884 KB Output is correct
112 Correct 3258 ms 125524 KB Output is correct
113 Correct 3305 ms 121640 KB Output is correct
114 Correct 3427 ms 119104 KB Output is correct
115 Correct 3434 ms 127064 KB Output is correct
116 Correct 3299 ms 132560 KB Output is correct
117 Correct 3140 ms 114492 KB Output is correct
118 Correct 3053 ms 120600 KB Output is correct
119 Correct 3297 ms 125040 KB Output is correct
120 Correct 3170 ms 123272 KB Output is correct
121 Correct 3386 ms 125516 KB Output is correct
122 Correct 3573 ms 128704 KB Output is correct
123 Correct 3647 ms 127260 KB Output is correct
124 Correct 3740 ms 121108 KB Output is correct
125 Correct 3167 ms 119572 KB Output is correct
126 Correct 3355 ms 120000 KB Output is correct
127 Correct 3023 ms 120328 KB Output is correct
128 Correct 3122 ms 116980 KB Output is correct
129 Correct 3186 ms 119160 KB Output is correct
130 Correct 3291 ms 112892 KB Output is correct
131 Correct 3214 ms 111368 KB Output is correct
132 Correct 3211 ms 111504 KB Output is correct
133 Correct 266 ms 57204 KB Output is correct
134 Correct 263 ms 57224 KB Output is correct
135 Correct 259 ms 57360 KB Output is correct
136 Correct 286 ms 59284 KB Output is correct
137 Correct 393 ms 66756 KB Output is correct
138 Correct 379 ms 66524 KB Output is correct
139 Correct 386 ms 67016 KB Output is correct
140 Correct 260 ms 57532 KB Output is correct
141 Correct 374 ms 66668 KB Output is correct
142 Correct 362 ms 66284 KB Output is correct
143 Correct 362 ms 66412 KB Output is correct
144 Correct 365 ms 66116 KB Output is correct
145 Correct 380 ms 66588 KB Output is correct
146 Correct 365 ms 66428 KB Output is correct
147 Correct 358 ms 66412 KB Output is correct
148 Correct 3167 ms 149096 KB Output is correct
149 Correct 3217 ms 153464 KB Output is correct
150 Correct 3089 ms 150104 KB Output is correct
151 Correct 2456 ms 153188 KB Output is correct
152 Correct 3153 ms 146776 KB Output is correct
153 Correct 3112 ms 149284 KB Output is correct
154 Correct 3463 ms 154176 KB Output is correct
155 Correct 3847 ms 166288 KB Output is correct
156 Correct 4017 ms 182744 KB Output is correct
157 Correct 3950 ms 184256 KB Output is correct
158 Correct 2352 ms 145460 KB Output is correct
159 Correct 4307 ms 230884 KB Output is correct
160 Correct 3946 ms 188588 KB Output is correct
161 Correct 3373 ms 150136 KB Output is correct
162 Correct 3482 ms 146776 KB Output is correct
163 Correct 3356 ms 146648 KB Output is correct
164 Correct 3055 ms 151184 KB Output is correct
165 Correct 3124 ms 148856 KB Output is correct
166 Correct 3020 ms 146924 KB Output is correct
167 Correct 3233 ms 146864 KB Output is correct
168 Correct 3194 ms 146036 KB Output is correct
169 Correct 3243 ms 148912 KB Output is correct
170 Correct 3210 ms 152952 KB Output is correct
171 Correct 3205 ms 153184 KB Output is correct
172 Correct 3272 ms 148780 KB Output is correct
173 Correct 3151 ms 148808 KB Output is correct
174 Correct 2966 ms 150288 KB Output is correct
175 Correct 3078 ms 151220 KB Output is correct
176 Correct 3131 ms 149048 KB Output is correct
177 Correct 3323 ms 152312 KB Output is correct
178 Correct 3293 ms 150128 KB Output is correct
179 Correct 3678 ms 148944 KB Output is correct
180 Correct 3332 ms 149128 KB Output is correct
181 Correct 3435 ms 151100 KB Output is correct
182 Correct 3207 ms 153780 KB Output is correct
183 Correct 3858 ms 168168 KB Output is correct
184 Execution timed out 6022 ms 299692 KB Time limit exceeded
185 Halted 0 ms 0 KB -