oj.uz

Submission #427680

# Submission time Handle Problem Language Result Execution time Memory
427680 2021-06-14T18:45:38 Z duality From Hacks to Snitches (BOI21_watchmen) C++11
80 / 100
 6000 ms 197416 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];
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 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);
    }
    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]++;
    }
    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)) 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;
                vector<LLI> dd(p[v].first,-1);
                priority_queue<LLI> H2;
                for (j = 0; j < ((((p[u].second.first-d) % p[u].first)+p[u].first) % p[u].first); j++) {
                    if (j == p[v].first) break;
                    dd[(d+j) % p[v].first] = d+j;
                }
                for (j = 0; j < p[v].first; j++) {
                    if (dd[j] != -1) H2.push(-dd[j]);
                }
                while (!H2.empty()) {
                    LLI d = -H2.top();
                    H2.pop();

                    if (d > dd[d % p[v].first]) continue;
                    if ((dd[(d+p[u].first) % p[v].first] == -1) || (d+p[u].first < dd[(d+p[u].first) % p[v].first])) {
                        dd[(d+p[u].first) % p[v].first] = d+p[u].first;
                        H2.push(-(d+p[u].first));
                    }
                }
                for (j = 0; j < p[v].first; j++) {
                    if (dd[j] != -1) {
                        LLI d2 = dd[j]+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:51:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         while ((pos[i] < adjList[i].size()) && (p[adjList[i][pos[i]]].first == 1)) pos[i]++;
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:66:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (i = done[u] ? pos[u]:0; i < adjList[u].size(); i++) {
      |                                      ~~^~~~~~~~~~~~~~~~~~~
watchmen.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
watchmen.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~
watchmen.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d",&K);
      |     ~~~~~^~~~~~~~~
watchmen.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         scanf("%d",&l);
      |         ~~~~~^~~~~~~~~
watchmen.cpp:41:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         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 45 ms 25156 KB Output is correct
2 Correct 130 ms 32136 KB Output is correct
3 Correct 134 ms 31892 KB Output is correct
4 Correct 169 ms 32200 KB Output is correct
5 Correct 17 ms 23816 KB Output is correct
6 Correct 130 ms 31892 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 25048 KB Output is correct
2 Correct 152 ms 32128 KB Output is correct
3 Correct 130 ms 31848 KB Output is correct
4 Correct 130 ms 32200 KB Output is correct
5 Correct 18 ms 24012 KB Output is correct
6 Correct 139 ms 31832 KB Output is correct
7 Correct 118 ms 31412 KB Output is correct
8 Correct 117 ms 31620 KB Output is correct
9 Correct 113 ms 31312 KB Output is correct
10 Correct 167 ms 31944 KB Output is correct
11 Correct 129 ms 31752 KB Output is correct
12 Correct 133 ms 31792 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 25048 KB Output is correct
2 Correct 152 ms 32128 KB Output is correct
3 Correct 130 ms 31848 KB Output is correct
4 Correct 130 ms 32200 KB Output is correct
5 Correct 18 ms 24012 KB Output is correct
6 Correct 139 ms 31832 KB Output is correct
7 Correct 118 ms 31412 KB Output is correct
8 Correct 117 ms 31620 KB Output is correct
9 Correct 113 ms 31312 KB Output is correct
10 Correct 167 ms 31944 KB Output is correct
11 Correct 129 ms 31752 KB Output is correct
12 Correct 133 ms 31792 KB Output is correct
13 Correct 46 ms 25092 KB Output is correct
14 Correct 142 ms 32232 KB Output is correct
15 Correct 126 ms 31868 KB Output is correct
16 Correct 143 ms 32244 KB Output is correct
17 Correct 20 ms 23936 KB Output is correct
18 Correct 144 ms 31940 KB Output is correct
19 Correct 139 ms 31496 KB Output is correct
20 Correct 123 ms 31688 KB Output is correct
21 Correct 136 ms 31344 KB Output is correct
22 Correct 149 ms 31884 KB Output is correct
23 Correct 126 ms 31724 KB Output is correct
24 Correct 120 ms 31692 KB Output is correct
25 Correct 3150 ms 76988 KB Output is correct
26 Correct 3196 ms 81356 KB Output is correct
27 Correct 3025 ms 77920 KB Output is correct
28 Correct 2219 ms 80784 KB Output is correct
29 Correct 3045 ms 74256 KB Output is correct
30 Correct 2989 ms 76988 KB Output is correct
31 Correct 3560 ms 81960 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 25048 KB Output is correct
2 Correct 152 ms 32128 KB Output is correct
3 Correct 130 ms 31848 KB Output is correct
4 Correct 130 ms 32200 KB Output is correct
5 Correct 18 ms 24012 KB Output is correct
6 Correct 139 ms 31832 KB Output is correct
7 Correct 118 ms 31412 KB Output is correct
8 Correct 117 ms 31620 KB Output is correct
9 Correct 113 ms 31312 KB Output is correct
10 Correct 167 ms 31944 KB Output is correct
11 Correct 129 ms 31752 KB Output is correct
12 Correct 133 ms 31792 KB Output is correct
13 Correct 46 ms 25092 KB Output is correct
14 Correct 142 ms 32232 KB Output is correct
15 Correct 126 ms 31868 KB Output is correct
16 Correct 143 ms 32244 KB Output is correct
17 Correct 20 ms 23936 KB Output is correct
18 Correct 144 ms 31940 KB Output is correct
19 Correct 139 ms 31496 KB Output is correct
20 Correct 123 ms 31688 KB Output is correct
21 Correct 136 ms 31344 KB Output is correct
22 Correct 149 ms 31884 KB Output is correct
23 Correct 126 ms 31724 KB Output is correct
24 Correct 120 ms 31692 KB Output is correct
25 Correct 3150 ms 76988 KB Output is correct
26 Correct 3196 ms 81356 KB Output is correct
27 Correct 3025 ms 77920 KB Output is correct
28 Correct 2219 ms 80784 KB Output is correct
29 Correct 3045 ms 74256 KB Output is correct
30 Correct 2989 ms 76988 KB Output is correct
31 Correct 3560 ms 81960 KB Output is correct
32 Correct 45 ms 25156 KB Output is correct
33 Correct 132 ms 32136 KB Output is correct
34 Correct 150 ms 31864 KB Output is correct
35 Correct 137 ms 32200 KB Output is correct
36 Correct 18 ms 24028 KB Output is correct
37 Correct 152 ms 31932 KB Output is correct
38 Correct 138 ms 31432 KB Output is correct
39 Correct 128 ms 31660 KB Output is correct
40 Correct 119 ms 31432 KB Output is correct
41 Correct 146 ms 31892 KB Output is correct
42 Correct 144 ms 31672 KB Output is correct
43 Correct 123 ms 31732 KB Output is correct
44 Correct 3443 ms 76956 KB Output is correct
45 Correct 3445 ms 81316 KB Output is correct
46 Correct 2777 ms 77916 KB Output is correct
47 Correct 2261 ms 80788 KB Output is correct
48 Correct 3042 ms 74240 KB Output is correct
49 Correct 2989 ms 77112 KB Output is correct
50 Correct 3343 ms 81876 KB Output is correct
51 Correct 3657 ms 94176 KB Output is correct
52 Correct 3707 ms 110644 KB Output is correct
53 Correct 3679 ms 112388 KB Output is correct
54 Correct 2130 ms 73080 KB Output is correct
55 Correct 3898 ms 158904 KB Output is correct
56 Correct 3543 ms 116732 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 25156 KB Output is correct
2 Correct 130 ms 32136 KB Output is correct
3 Correct 134 ms 31892 KB Output is correct
4 Correct 169 ms 32200 KB Output is correct
5 Correct 17 ms 23816 KB Output is correct
6 Correct 130 ms 31892 KB Output is correct
7 Correct 45 ms 25048 KB Output is correct
8 Correct 152 ms 32128 KB Output is correct
9 Correct 130 ms 31848 KB Output is correct
10 Correct 130 ms 32200 KB Output is correct
11 Correct 18 ms 24012 KB Output is correct
12 Correct 139 ms 31832 KB Output is correct
13 Correct 118 ms 31412 KB Output is correct
14 Correct 117 ms 31620 KB Output is correct
15 Correct 113 ms 31312 KB Output is correct
16 Correct 167 ms 31944 KB Output is correct
17 Correct 129 ms 31752 KB Output is correct
18 Correct 133 ms 31792 KB Output is correct
19 Correct 17 ms 23768 KB Output is correct
20 Correct 16 ms 23796 KB Output is correct
21 Correct 18 ms 23804 KB Output is correct
22 Correct 56 ms 25112 KB Output is correct
23 Correct 126 ms 32128 KB Output is correct
24 Correct 123 ms 31924 KB Output is correct
25 Correct 168 ms 32288 KB Output is correct
26 Correct 17 ms 23940 KB Output is correct
27 Correct 135 ms 31860 KB Output is correct
28 Correct 117 ms 31420 KB Output is correct
29 Correct 118 ms 31700 KB Output is correct
30 Correct 155 ms 31364 KB Output is correct
31 Correct 145 ms 31876 KB Output is correct
32 Correct 125 ms 31684 KB Output is correct
33 Correct 120 ms 31720 KB Output is correct
34 Correct 3183 ms 78172 KB Output is correct
35 Correct 3162 ms 74500 KB Output is correct
36 Correct 3295 ms 74656 KB Output is correct
37 Correct 2924 ms 79180 KB Output is correct
38 Correct 3254 ms 115184 KB Output is correct
39 Correct 2781 ms 113352 KB Output is correct
40 Correct 2890 ms 113304 KB Output is correct
41 Correct 2783 ms 112428 KB Output is correct
42 Correct 2904 ms 115264 KB Output is correct
43 Correct 3088 ms 119420 KB Output is correct
44 Correct 3117 ms 119604 KB Output is correct
45 Correct 3272 ms 115304 KB Output is correct
46 Correct 2970 ms 115228 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 25156 KB Output is correct
2 Correct 130 ms 32136 KB Output is correct
3 Correct 134 ms 31892 KB Output is correct
4 Correct 169 ms 32200 KB Output is correct
5 Correct 17 ms 23816 KB Output is correct
6 Correct 130 ms 31892 KB Output is correct
7 Correct 45 ms 25048 KB Output is correct
8 Correct 152 ms 32128 KB Output is correct
9 Correct 130 ms 31848 KB Output is correct
10 Correct 130 ms 32200 KB Output is correct
11 Correct 18 ms 24012 KB Output is correct
12 Correct 139 ms 31832 KB Output is correct
13 Correct 118 ms 31412 KB Output is correct
14 Correct 117 ms 31620 KB Output is correct
15 Correct 113 ms 31312 KB Output is correct
16 Correct 167 ms 31944 KB Output is correct
17 Correct 129 ms 31752 KB Output is correct
18 Correct 133 ms 31792 KB Output is correct
19 Correct 46 ms 25092 KB Output is correct
20 Correct 142 ms 32232 KB Output is correct
21 Correct 126 ms 31868 KB Output is correct
22 Correct 143 ms 32244 KB Output is correct
23 Correct 20 ms 23936 KB Output is correct
24 Correct 144 ms 31940 KB Output is correct
25 Correct 139 ms 31496 KB Output is correct
26 Correct 123 ms 31688 KB Output is correct
27 Correct 136 ms 31344 KB Output is correct
28 Correct 149 ms 31884 KB Output is correct
29 Correct 126 ms 31724 KB Output is correct
30 Correct 120 ms 31692 KB Output is correct
31 Correct 3150 ms 76988 KB Output is correct
32 Correct 3196 ms 81356 KB Output is correct
33 Correct 3025 ms 77920 KB Output is correct
34 Correct 2219 ms 80784 KB Output is correct
35 Correct 3045 ms 74256 KB Output is correct
36 Correct 2989 ms 76988 KB Output is correct
37 Correct 3560 ms 81960 KB Output is correct
38 Correct 17 ms 23768 KB Output is correct
39 Correct 16 ms 23796 KB Output is correct
40 Correct 18 ms 23804 KB Output is correct
41 Correct 56 ms 25112 KB Output is correct
42 Correct 126 ms 32128 KB Output is correct
43 Correct 123 ms 31924 KB Output is correct
44 Correct 168 ms 32288 KB Output is correct
45 Correct 17 ms 23940 KB Output is correct
46 Correct 135 ms 31860 KB Output is correct
47 Correct 117 ms 31420 KB Output is correct
48 Correct 118 ms 31700 KB Output is correct
49 Correct 155 ms 31364 KB Output is correct
50 Correct 145 ms 31876 KB Output is correct
51 Correct 125 ms 31684 KB Output is correct
52 Correct 120 ms 31720 KB Output is correct
53 Correct 3183 ms 78172 KB Output is correct
54 Correct 3162 ms 74500 KB Output is correct
55 Correct 3295 ms 74656 KB Output is correct
56 Correct 2924 ms 79180 KB Output is correct
57 Correct 3254 ms 115184 KB Output is correct
58 Correct 2781 ms 113352 KB Output is correct
59 Correct 2890 ms 113304 KB Output is correct
60 Correct 2783 ms 112428 KB Output is correct
61 Correct 2904 ms 115264 KB Output is correct
62 Correct 3088 ms 119420 KB Output is correct
63 Correct 3117 ms 119604 KB Output is correct
64 Correct 3272 ms 115304 KB Output is correct
65 Correct 2970 ms 115228 KB Output is correct
66 Correct 13 ms 23716 KB Output is correct
67 Correct 17 ms 23756 KB Output is correct
68 Correct 20 ms 23724 KB Output is correct
69 Correct 42 ms 25668 KB Output is correct
70 Correct 135 ms 33288 KB Output is correct
71 Correct 130 ms 33096 KB Output is correct
72 Correct 209 ms 33352 KB Output is correct
73 Correct 27 ms 23884 KB Output is correct
74 Correct 139 ms 33092 KB Output is correct
75 Correct 127 ms 32540 KB Output is correct
76 Correct 149 ms 32836 KB Output is correct
77 Correct 166 ms 32592 KB Output is correct
78 Correct 158 ms 33096 KB Output is correct
79 Correct 135 ms 32896 KB Output is correct
80 Correct 160 ms 32908 KB Output is correct
81 Correct 3390 ms 115492 KB Output is correct
82 Correct 3094 ms 119828 KB Output is correct
83 Correct 3347 ms 116564 KB Output is correct
84 Correct 2520 ms 119304 KB Output is correct
85 Correct 2997 ms 113096 KB Output is correct
86 Correct 2908 ms 115436 KB Output is correct
87 Correct 3016 ms 120380 KB Output is correct
88 Correct 2995 ms 116544 KB Output is correct
89 Correct 3357 ms 113032 KB Output is correct
90 Correct 3312 ms 113180 KB Output is correct
91 Correct 2954 ms 117592 KB Output is correct
92 Correct 3264 ms 115224 KB Output is correct
93 Correct 2940 ms 113280 KB Output is correct
94 Correct 2847 ms 113248 KB Output is correct
95 Correct 2818 ms 112628 KB Output is correct
96 Correct 3168 ms 115276 KB Output is correct
97 Correct 2971 ms 119376 KB Output is correct
98 Correct 2901 ms 119744 KB Output is correct
99 Correct 2997 ms 115328 KB Output is correct
100 Correct 2867 ms 115228 KB Output is correct
101 Correct 3002 ms 116632 KB Output is correct
102 Correct 2737 ms 117576 KB Output is correct
103 Correct 2987 ms 115444 KB Output is correct
104 Correct 3228 ms 118380 KB Output is correct
105 Correct 2985 ms 116540 KB Output is correct
106 Correct 3287 ms 115340 KB Output is correct
107 Correct 3071 ms 115516 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 25156 KB Output is correct
2 Correct 130 ms 32136 KB Output is correct
3 Correct 134 ms 31892 KB Output is correct
4 Correct 169 ms 32200 KB Output is correct
5 Correct 17 ms 23816 KB Output is correct
6 Correct 130 ms 31892 KB Output is correct
7 Correct 45 ms 25048 KB Output is correct
8 Correct 152 ms 32128 KB Output is correct
9 Correct 130 ms 31848 KB Output is correct
10 Correct 130 ms 32200 KB Output is correct
11 Correct 18 ms 24012 KB Output is correct
12 Correct 139 ms 31832 KB Output is correct
13 Correct 118 ms 31412 KB Output is correct
14 Correct 117 ms 31620 KB Output is correct
15 Correct 113 ms 31312 KB Output is correct
16 Correct 167 ms 31944 KB Output is correct
17 Correct 129 ms 31752 KB Output is correct
18 Correct 133 ms 31792 KB Output is correct
19 Correct 46 ms 25092 KB Output is correct
20 Correct 142 ms 32232 KB Output is correct
21 Correct 126 ms 31868 KB Output is correct
22 Correct 143 ms 32244 KB Output is correct
23 Correct 20 ms 23936 KB Output is correct
24 Correct 144 ms 31940 KB Output is correct
25 Correct 139 ms 31496 KB Output is correct
26 Correct 123 ms 31688 KB Output is correct
27 Correct 136 ms 31344 KB Output is correct
28 Correct 149 ms 31884 KB Output is correct
29 Correct 126 ms 31724 KB Output is correct
30 Correct 120 ms 31692 KB Output is correct
31 Correct 3150 ms 76988 KB Output is correct
32 Correct 3196 ms 81356 KB Output is correct
33 Correct 3025 ms 77920 KB Output is correct
34 Correct 2219 ms 80784 KB Output is correct
35 Correct 3045 ms 74256 KB Output is correct
36 Correct 2989 ms 76988 KB Output is correct
37 Correct 3560 ms 81960 KB Output is correct
38 Correct 45 ms 25156 KB Output is correct
39 Correct 132 ms 32136 KB Output is correct
40 Correct 150 ms 31864 KB Output is correct
41 Correct 137 ms 32200 KB Output is correct
42 Correct 18 ms 24028 KB Output is correct
43 Correct 152 ms 31932 KB Output is correct
44 Correct 138 ms 31432 KB Output is correct
45 Correct 128 ms 31660 KB Output is correct
46 Correct 119 ms 31432 KB Output is correct
47 Correct 146 ms 31892 KB Output is correct
48 Correct 144 ms 31672 KB Output is correct
49 Correct 123 ms 31732 KB Output is correct
50 Correct 3443 ms 76956 KB Output is correct
51 Correct 3445 ms 81316 KB Output is correct
52 Correct 2777 ms 77916 KB Output is correct
53 Correct 2261 ms 80788 KB Output is correct
54 Correct 3042 ms 74240 KB Output is correct
55 Correct 2989 ms 77112 KB Output is correct
56 Correct 3343 ms 81876 KB Output is correct
57 Correct 3657 ms 94176 KB Output is correct
58 Correct 3707 ms 110644 KB Output is correct
59 Correct 3679 ms 112388 KB Output is correct
60 Correct 2130 ms 73080 KB Output is correct
61 Correct 3898 ms 158904 KB Output is correct
62 Correct 3543 ms 116732 KB Output is correct
63 Correct 17 ms 23768 KB Output is correct
64 Correct 16 ms 23796 KB Output is correct
65 Correct 18 ms 23804 KB Output is correct
66 Correct 56 ms 25112 KB Output is correct
67 Correct 126 ms 32128 KB Output is correct
68 Correct 123 ms 31924 KB Output is correct
69 Correct 168 ms 32288 KB Output is correct
70 Correct 17 ms 23940 KB Output is correct
71 Correct 135 ms 31860 KB Output is correct
72 Correct 117 ms 31420 KB Output is correct
73 Correct 118 ms 31700 KB Output is correct
74 Correct 155 ms 31364 KB Output is correct
75 Correct 145 ms 31876 KB Output is correct
76 Correct 125 ms 31684 KB Output is correct
77 Correct 120 ms 31720 KB Output is correct
78 Correct 3183 ms 78172 KB Output is correct
79 Correct 3162 ms 74500 KB Output is correct
80 Correct 3295 ms 74656 KB Output is correct
81 Correct 2924 ms 79180 KB Output is correct
82 Correct 3254 ms 115184 KB Output is correct
83 Correct 2781 ms 113352 KB Output is correct
84 Correct 2890 ms 113304 KB Output is correct
85 Correct 2783 ms 112428 KB Output is correct
86 Correct 2904 ms 115264 KB Output is correct
87 Correct 3088 ms 119420 KB Output is correct
88 Correct 3117 ms 119604 KB Output is correct
89 Correct 3272 ms 115304 KB Output is correct
90 Correct 2970 ms 115228 KB Output is correct
91 Correct 13 ms 23716 KB Output is correct
92 Correct 17 ms 23756 KB Output is correct
93 Correct 20 ms 23724 KB Output is correct
94 Correct 42 ms 25668 KB Output is correct
95 Correct 135 ms 33288 KB Output is correct
96 Correct 130 ms 33096 KB Output is correct
97 Correct 209 ms 33352 KB Output is correct
98 Correct 27 ms 23884 KB Output is correct
99 Correct 139 ms 33092 KB Output is correct
100 Correct 127 ms 32540 KB Output is correct
101 Correct 149 ms 32836 KB Output is correct
102 Correct 166 ms 32592 KB Output is correct
103 Correct 158 ms 33096 KB Output is correct
104 Correct 135 ms 32896 KB Output is correct
105 Correct 160 ms 32908 KB Output is correct
106 Correct 3390 ms 115492 KB Output is correct
107 Correct 3094 ms 119828 KB Output is correct
108 Correct 3347 ms 116564 KB Output is correct
109 Correct 2520 ms 119304 KB Output is correct
110 Correct 2997 ms 113096 KB Output is correct
111 Correct 2908 ms 115436 KB Output is correct
112 Correct 3016 ms 120380 KB Output is correct
113 Correct 2995 ms 116544 KB Output is correct
114 Correct 3357 ms 113032 KB Output is correct
115 Correct 3312 ms 113180 KB Output is correct
116 Correct 2954 ms 117592 KB Output is correct
117 Correct 3264 ms 115224 KB Output is correct
118 Correct 2940 ms 113280 KB Output is correct
119 Correct 2847 ms 113248 KB Output is correct
120 Correct 2818 ms 112628 KB Output is correct
121 Correct 3168 ms 115276 KB Output is correct
122 Correct 2971 ms 119376 KB Output is correct
123 Correct 2901 ms 119744 KB Output is correct
124 Correct 2997 ms 115328 KB Output is correct
125 Correct 2867 ms 115228 KB Output is correct
126 Correct 3002 ms 116632 KB Output is correct
127 Correct 2737 ms 117576 KB Output is correct
128 Correct 2987 ms 115444 KB Output is correct
129 Correct 3228 ms 118380 KB Output is correct
130 Correct 2985 ms 116540 KB Output is correct
131 Correct 3287 ms 115340 KB Output is correct
132 Correct 3071 ms 115516 KB Output is correct
133 Correct 19 ms 23856 KB Output is correct
134 Correct 17 ms 23756 KB Output is correct
135 Correct 17 ms 23756 KB Output is correct
136 Correct 45 ms 25668 KB Output is correct
137 Correct 138 ms 33296 KB Output is correct
138 Correct 126 ms 33056 KB Output is correct
139 Correct 133 ms 33392 KB Output is correct
140 Correct 17 ms 23924 KB Output is correct
141 Correct 139 ms 33056 KB Output is correct
142 Correct 121 ms 32568 KB Output is correct
143 Correct 126 ms 32816 KB Output is correct
144 Correct 122 ms 32584 KB Output is correct
145 Correct 126 ms 33112 KB Output is correct
146 Correct 125 ms 32928 KB Output is correct
147 Correct 127 ms 32824 KB Output is correct
148 Correct 3024 ms 115716 KB Output is correct
149 Correct 2924 ms 119860 KB Output is correct
150 Correct 2645 ms 116500 KB Output is correct
151 Correct 2126 ms 119308 KB Output is correct
152 Correct 2846 ms 113164 KB Output is correct
153 Correct 2718 ms 115348 KB Output is correct
154 Correct 3081 ms 120364 KB Output is correct
155 Correct 3448 ms 132608 KB Output is correct
156 Correct 3713 ms 149136 KB Output is correct
157 Correct 3772 ms 150668 KB Output is correct
158 Correct 2152 ms 111508 KB Output is correct
159 Correct 3886 ms 197416 KB Output is correct
160 Correct 3563 ms 155356 KB Output is correct
161 Correct 3077 ms 116640 KB Output is correct
162 Correct 3218 ms 113016 KB Output is correct
163 Correct 3307 ms 113172 KB Output is correct
164 Correct 2801 ms 117544 KB Output is correct
165 Correct 3092 ms 115192 KB Output is correct
166 Correct 2896 ms 113452 KB Output is correct
167 Correct 2832 ms 113344 KB Output is correct
168 Correct 2823 ms 112400 KB Output is correct
169 Correct 3174 ms 115300 KB Output is correct
170 Correct 3138 ms 119184 KB Output is correct
171 Correct 3302 ms 119652 KB Output is correct
172 Correct 3234 ms 115120 KB Output is correct
173 Correct 3011 ms 115320 KB Output is correct
174 Correct 3152 ms 116520 KB Output is correct
175 Correct 2910 ms 117640 KB Output is correct
176 Correct 3145 ms 115136 KB Output is correct
177 Correct 3270 ms 118048 KB Output is correct
178 Correct 3166 ms 116076 KB Output is correct
179 Correct 3398 ms 114872 KB Output is correct
180 Correct 3028 ms 115020 KB Output is correct
181 Correct 3253 ms 117180 KB Output is correct
182 Correct 2955 ms 119316 KB Output is correct
183 Correct 3716 ms 134008 KB Output is correct
184 Execution timed out 6091 ms 192160 KB Time limit exceeded
185 Halted 0 ms 0 KB -