#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const int dx[] = {-1,0,0,1};
const int dy[] = {0,1,-1,0};
vector<int> AdjList[200005];
ii EdgeList[800005];
ii EdgeList2[800005];
map<ii, int> indx;
map<ii, int> indx2;
map<ii, int> indxEdge;
map<ii, int> indxBench;
vector<int> AdjListBench[800005];
set<int> AdjListRoad[200005];
int degBench[800005];
ii benchXY[800005];
mt19937 rng(1);
struct Dinic{
static const int MAX_E = 1000005;
static const int MAX_V = 1000005;
// Edge List
ii EdgeList[MAX_E<<1];
int flow[MAX_E<<1];
int capacity[MAX_E<<1];
vector<int> AdjList[MAX_V];
int level[MAX_V];
int ptr[MAX_V];
int E = 0;
int s, t;
Dinic(int _s, int _t){
s = _s;
t = _t;
}
void add_edge(int u, int v, int c){
EdgeList[E] = ii(u, v);
EdgeList[E+1] = ii(v, u);
flow[E] = 0;
flow[E+1] = 0;
capacity[E] = c;
capacity[E+1] = 0;
AdjList[u].push_back(E);
AdjList[v].push_back(E+1);
E += 2;
}
bool bfs(){
memset(level, -1, sizeof(level));
queue<int> q;
level[s] = 0;
q.push(s);
while(!q.empty()){
int u = q.front(); q.pop();
for(int indx: AdjList[u]){
int v = EdgeList[indx].second;
if(level[v] == -1 && capacity[indx] > flow[indx]){
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[t] != -1;
}
int dfs(int u, int flowToSend){
if(u == t){return flowToSend;}
if(flowToSend == 0){return 0;}
while(ptr[u] < (int)AdjList[u].size()){
int indx = AdjList[u][ptr[u]];
int v = EdgeList[indx].second;
if(capacity[indx] > flow[indx] && level[v] == level[u] + 1){
int nxtFlow = min(flowToSend, capacity[indx] - flow[indx]);
int flowSent = dfs(v, nxtFlow);
if(flowSent > 0){
flow[indx] += flowSent; // flow from u to v
flow[indx^1] -= flowSent; // flow from v to u
return flowSent;
}
}
ptr[u] ++;
}
return 0;
}
int findMaxFlow(){
int maxFlow = 0;
while(1){
if(!bfs()){return maxFlow;}
memset(ptr, 0, sizeof(ptr));
while(1){
int temp = dfs(s, INT_MAX);
maxFlow += temp;
if(temp == 0){break;}
}
}
}
};
struct UnionFind{
vector<int> p;
vector<int> rank1;
void init(int n){
p.assign(n, 0);
rank1.assign(n, 0);
for(int i = 0; i < n; i ++){
p[i] = i;
rank1[i] = 0;
}
}
int findSet(int i){
return (p[i] == i) ? i : (p[i] = findSet(p[i]));
}
bool isSameSet(int i, int j){
return findSet(i) == findSet(j);
}
void unionSet(int i, int j){
int x = findSet(i);
int y = findSet(j);
if(x != y){
if(rank1[x] > rank1[y]){
p[y] = x;
}else{
p[x] = y;
if(rank1[x] == rank1[y]){
rank1[y] ++;
}
}
}
}
};
int p[200005];
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = (int)x.size();
if (n == 1) {
build({}, {}, {}, {});
return 1;
}
vector<int> U(n-1);
vector<int> V(n-1);
vector<int> A(n-1);
vector<int> B(n-1);
for(int i = 0; i < n; i ++){
indx[ii(x[i], y[i])] = i;
}
for(int i = 0; i < n; i ++){
indx2[ii(y[i], x[i])] = i;
}
int cnt3 = 0;
for(pair<ii, int> temp: indx2){
p[cnt3 ++] = temp.second;
}
int m = 0;
for(int i = 0; i < n; i ++){
int i2 = p[i];
for(int k: {0, 3}){
int nx = x[i2] + 2*dx[k];
int ny = y[i2] + 2*dy[k];
if(indx.find(ii(nx, ny)) != indx.end()){
int j = indx[ii(nx, ny)];
EdgeList[m ++] = ii(i2, j);
}
}
}
for(int i = 0; i < n; i ++){
int i2 = p[i];
for(int k: {2, 1}){
int nx = x[i2] + 2*dx[k];
int ny = y[i2] + 2*dy[k];
if(indx.find(ii(nx, ny)) != indx.end()){
int j = indx[ii(nx, ny)];
EdgeList[m ++] = ii(i2, j);
}
}
}
UnionFind* uf = new UnionFind();
while(1){
uf->init(n);
int cnt = 0;
for(int i = 0; i < m; i ++){
int u, v;
tie(u, v) = EdgeList[i];
if(!uf->isSameSet(u, v)){
uf->unionSet(u, v);
AdjList[u].push_back(v);
AdjList[v].push_back(u);
EdgeList2[cnt] = ii(u, v);
indxEdge[ii(u, v)] = cnt;
cnt ++;
}
}
if(cnt != n-1){
return 0;
}
int benches = 0;
memset(degBench, 0, sizeof(degBench));
for(int i = 0; i < n-1; i ++){
int u, v;
tie(u, v) = EdgeList2[i];
int x2 = (x[u] + x[v])/2;
int y2 = (y[u] + y[v])/2;
for(int k = 0; k < 4; k ++){
int nx = x2 + dx[k];
int ny = y2 + dy[k];
if(nx%2 == 1 && ny%2 == 1){
int indx2 = benches;
if(indxBench.find(ii(nx, ny)) != indxBench.end()){
indx2 = indxBench[ii(nx, ny)];
}else{
benchXY[benches] = ii(nx, ny);
indxBench[ii(nx, ny)] = benches;
//printf("bench %d; (%d, %d)\n", benches, nx, ny);
benches ++;
}
AdjListBench[indx2].push_back(i);
AdjListRoad[i].insert(indx2);
//printf("road %d; bench %d\n", i, indx2);
degBench[i] ++;
}
}
}
int S = n+benches;
int T = n+benches+1;
Dinic* mf = new Dinic(S, T);
for(int i = 0; i < n; i ++){
mf->add_edge(S, i, 1);
}
for(int i = 0; i < benches; i ++){
mf->add_edge(n+i, T, 1);
}
for(int i = 0; i < n; i ++){
for(int j: AdjListRoad[i]){
mf->add_edge(i, n+j, 1);
}
}
int res = mf->findMaxFlow();
//printf("res=%d\n", res);
if(res != n-1){
shuffle(EdgeList, EdgeList+m, rng);
continue;
}
int cnt2 = 0;
for(int i = 0; i < mf->E; i ++){
int u, v;
tie(u, v) = mf->EdgeList[i];
//printf("u=%d v=%d\n", u, v);
if(u >= n){continue;}
if(mf->flow[i] > 0){
tie(U[cnt2], V[cnt2]) = EdgeList2[u];
tie(A[cnt2], B[cnt2]) = benchXY[v-n];
cnt2 ++;
}
}
if(cnt2 == n-1){
build(U, V, A, B);
return 1;
}
shuffle(EdgeList, EdgeList+m, rng);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
33100 KB |
Output is correct |
2 |
Correct |
46 ms |
83268 KB |
Output is correct |
3 |
Correct |
20 ms |
33100 KB |
Output is correct |
4 |
Correct |
47 ms |
83292 KB |
Output is correct |
5 |
Correct |
47 ms |
83228 KB |
Output is correct |
6 |
Correct |
20 ms |
33160 KB |
Output is correct |
7 |
Correct |
21 ms |
33120 KB |
Output is correct |
8 |
Correct |
21 ms |
33164 KB |
Output is correct |
9 |
Correct |
635 ms |
163192 KB |
Output is correct |
10 |
Correct |
79 ms |
91460 KB |
Output is correct |
11 |
Correct |
253 ms |
126548 KB |
Output is correct |
12 |
Correct |
96 ms |
95556 KB |
Output is correct |
13 |
Correct |
97 ms |
45756 KB |
Output is correct |
14 |
Correct |
23 ms |
33484 KB |
Output is correct |
15 |
Correct |
26 ms |
33816 KB |
Output is correct |
16 |
Correct |
564 ms |
163144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
33100 KB |
Output is correct |
2 |
Correct |
46 ms |
83268 KB |
Output is correct |
3 |
Correct |
20 ms |
33100 KB |
Output is correct |
4 |
Correct |
47 ms |
83292 KB |
Output is correct |
5 |
Correct |
47 ms |
83228 KB |
Output is correct |
6 |
Correct |
20 ms |
33160 KB |
Output is correct |
7 |
Correct |
21 ms |
33120 KB |
Output is correct |
8 |
Correct |
21 ms |
33164 KB |
Output is correct |
9 |
Correct |
635 ms |
163192 KB |
Output is correct |
10 |
Correct |
79 ms |
91460 KB |
Output is correct |
11 |
Correct |
253 ms |
126548 KB |
Output is correct |
12 |
Correct |
96 ms |
95556 KB |
Output is correct |
13 |
Correct |
97 ms |
45756 KB |
Output is correct |
14 |
Correct |
23 ms |
33484 KB |
Output is correct |
15 |
Correct |
26 ms |
33816 KB |
Output is correct |
16 |
Correct |
564 ms |
163144 KB |
Output is correct |
17 |
Correct |
45 ms |
83232 KB |
Output is correct |
18 |
Correct |
51 ms |
83288 KB |
Output is correct |
19 |
Correct |
55 ms |
83212 KB |
Output is correct |
20 |
Correct |
48 ms |
83276 KB |
Output is correct |
21 |
Correct |
20 ms |
33228 KB |
Output is correct |
22 |
Correct |
44 ms |
83292 KB |
Output is correct |
23 |
Correct |
1337 ms |
214160 KB |
Output is correct |
24 |
Correct |
44 ms |
83272 KB |
Output is correct |
25 |
Correct |
50 ms |
84108 KB |
Output is correct |
26 |
Correct |
25 ms |
33968 KB |
Output is correct |
27 |
Correct |
29 ms |
34368 KB |
Output is correct |
28 |
Correct |
477 ms |
135612 KB |
Output is correct |
29 |
Correct |
710 ms |
161780 KB |
Output is correct |
30 |
Correct |
1078 ms |
187900 KB |
Output is correct |
31 |
Correct |
1336 ms |
214096 KB |
Output is correct |
32 |
Correct |
47 ms |
83192 KB |
Output is correct |
33 |
Correct |
44 ms |
83248 KB |
Output is correct |
34 |
Correct |
45 ms |
83204 KB |
Output is correct |
35 |
Correct |
21 ms |
33084 KB |
Output is correct |
36 |
Correct |
20 ms |
33100 KB |
Output is correct |
37 |
Correct |
50 ms |
83304 KB |
Output is correct |
38 |
Correct |
47 ms |
83232 KB |
Output is correct |
39 |
Correct |
48 ms |
83300 KB |
Output is correct |
40 |
Correct |
47 ms |
83396 KB |
Output is correct |
41 |
Correct |
21 ms |
33100 KB |
Output is correct |
42 |
Correct |
49 ms |
83276 KB |
Output is correct |
43 |
Correct |
26 ms |
33740 KB |
Output is correct |
44 |
Correct |
30 ms |
33996 KB |
Output is correct |
45 |
Correct |
571 ms |
153624 KB |
Output is correct |
46 |
Correct |
925 ms |
185824 KB |
Output is correct |
47 |
Correct |
916 ms |
185664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
33100 KB |
Output is correct |
2 |
Correct |
46 ms |
83268 KB |
Output is correct |
3 |
Correct |
20 ms |
33100 KB |
Output is correct |
4 |
Correct |
47 ms |
83292 KB |
Output is correct |
5 |
Correct |
47 ms |
83228 KB |
Output is correct |
6 |
Correct |
20 ms |
33160 KB |
Output is correct |
7 |
Correct |
21 ms |
33120 KB |
Output is correct |
8 |
Correct |
21 ms |
33164 KB |
Output is correct |
9 |
Correct |
635 ms |
163192 KB |
Output is correct |
10 |
Correct |
79 ms |
91460 KB |
Output is correct |
11 |
Correct |
253 ms |
126548 KB |
Output is correct |
12 |
Correct |
96 ms |
95556 KB |
Output is correct |
13 |
Correct |
97 ms |
45756 KB |
Output is correct |
14 |
Correct |
23 ms |
33484 KB |
Output is correct |
15 |
Correct |
26 ms |
33816 KB |
Output is correct |
16 |
Correct |
564 ms |
163144 KB |
Output is correct |
17 |
Correct |
45 ms |
83232 KB |
Output is correct |
18 |
Correct |
51 ms |
83288 KB |
Output is correct |
19 |
Correct |
55 ms |
83212 KB |
Output is correct |
20 |
Correct |
48 ms |
83276 KB |
Output is correct |
21 |
Correct |
20 ms |
33228 KB |
Output is correct |
22 |
Correct |
44 ms |
83292 KB |
Output is correct |
23 |
Correct |
1337 ms |
214160 KB |
Output is correct |
24 |
Correct |
44 ms |
83272 KB |
Output is correct |
25 |
Correct |
50 ms |
84108 KB |
Output is correct |
26 |
Correct |
25 ms |
33968 KB |
Output is correct |
27 |
Correct |
29 ms |
34368 KB |
Output is correct |
28 |
Correct |
477 ms |
135612 KB |
Output is correct |
29 |
Correct |
710 ms |
161780 KB |
Output is correct |
30 |
Correct |
1078 ms |
187900 KB |
Output is correct |
31 |
Correct |
1336 ms |
214096 KB |
Output is correct |
32 |
Correct |
47 ms |
83192 KB |
Output is correct |
33 |
Correct |
44 ms |
83248 KB |
Output is correct |
34 |
Correct |
45 ms |
83204 KB |
Output is correct |
35 |
Correct |
21 ms |
33084 KB |
Output is correct |
36 |
Correct |
20 ms |
33100 KB |
Output is correct |
37 |
Correct |
50 ms |
83304 KB |
Output is correct |
38 |
Correct |
47 ms |
83232 KB |
Output is correct |
39 |
Correct |
48 ms |
83300 KB |
Output is correct |
40 |
Correct |
47 ms |
83396 KB |
Output is correct |
41 |
Correct |
21 ms |
33100 KB |
Output is correct |
42 |
Correct |
49 ms |
83276 KB |
Output is correct |
43 |
Correct |
26 ms |
33740 KB |
Output is correct |
44 |
Correct |
30 ms |
33996 KB |
Output is correct |
45 |
Correct |
571 ms |
153624 KB |
Output is correct |
46 |
Correct |
925 ms |
185824 KB |
Output is correct |
47 |
Correct |
916 ms |
185664 KB |
Output is correct |
48 |
Correct |
55 ms |
83240 KB |
Output is correct |
49 |
Correct |
45 ms |
83204 KB |
Output is correct |
50 |
Correct |
46 ms |
83272 KB |
Output is correct |
51 |
Correct |
48 ms |
83320 KB |
Output is correct |
52 |
Correct |
48 ms |
83324 KB |
Output is correct |
53 |
Correct |
52 ms |
83316 KB |
Output is correct |
54 |
Correct |
55 ms |
83200 KB |
Output is correct |
55 |
Correct |
1487 ms |
214596 KB |
Output is correct |
56 |
Correct |
48 ms |
83324 KB |
Output is correct |
57 |
Correct |
62 ms |
84484 KB |
Output is correct |
58 |
Correct |
77 ms |
87364 KB |
Output is correct |
59 |
Correct |
48 ms |
36108 KB |
Output is correct |
60 |
Correct |
645 ms |
151944 KB |
Output is correct |
61 |
Correct |
888 ms |
172396 KB |
Output is correct |
62 |
Correct |
1147 ms |
191708 KB |
Output is correct |
63 |
Correct |
1473 ms |
214616 KB |
Output is correct |
64 |
Correct |
23 ms |
33100 KB |
Output is correct |
65 |
Correct |
52 ms |
83256 KB |
Output is correct |
66 |
Correct |
20 ms |
33100 KB |
Output is correct |
67 |
Correct |
1404 ms |
243028 KB |
Output is correct |
68 |
Correct |
1455 ms |
242984 KB |
Output is correct |
69 |
Correct |
1486 ms |
242192 KB |
Output is correct |
70 |
Correct |
28 ms |
34252 KB |
Output is correct |
71 |
Correct |
37 ms |
35380 KB |
Output is correct |
72 |
Correct |
592 ms |
153332 KB |
Output is correct |
73 |
Correct |
1042 ms |
188572 KB |
Output is correct |
74 |
Correct |
1343 ms |
223304 KB |
Output is correct |
75 |
Correct |
1421 ms |
225340 KB |
Output is correct |
76 |
Correct |
1334 ms |
243000 KB |
Output is correct |
77 |
Correct |
34 ms |
34572 KB |
Output is correct |
78 |
Correct |
46 ms |
35672 KB |
Output is correct |
79 |
Correct |
685 ms |
153364 KB |
Output is correct |
80 |
Correct |
995 ms |
188652 KB |
Output is correct |
81 |
Correct |
1344 ms |
223588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
33100 KB |
Output is correct |
2 |
Correct |
46 ms |
83268 KB |
Output is correct |
3 |
Correct |
20 ms |
33100 KB |
Output is correct |
4 |
Correct |
47 ms |
83292 KB |
Output is correct |
5 |
Correct |
47 ms |
83228 KB |
Output is correct |
6 |
Correct |
20 ms |
33160 KB |
Output is correct |
7 |
Correct |
21 ms |
33120 KB |
Output is correct |
8 |
Correct |
21 ms |
33164 KB |
Output is correct |
9 |
Correct |
635 ms |
163192 KB |
Output is correct |
10 |
Correct |
79 ms |
91460 KB |
Output is correct |
11 |
Correct |
253 ms |
126548 KB |
Output is correct |
12 |
Correct |
96 ms |
95556 KB |
Output is correct |
13 |
Correct |
97 ms |
45756 KB |
Output is correct |
14 |
Correct |
23 ms |
33484 KB |
Output is correct |
15 |
Correct |
26 ms |
33816 KB |
Output is correct |
16 |
Correct |
564 ms |
163144 KB |
Output is correct |
17 |
Correct |
47 ms |
83264 KB |
Output is correct |
18 |
Correct |
53 ms |
83276 KB |
Output is correct |
19 |
Correct |
23 ms |
33176 KB |
Output is correct |
20 |
Correct |
1275 ms |
213732 KB |
Output is correct |
21 |
Correct |
1331 ms |
213796 KB |
Output is correct |
22 |
Correct |
1369 ms |
213780 KB |
Output is correct |
23 |
Correct |
1084 ms |
219012 KB |
Output is correct |
24 |
Correct |
596 ms |
66828 KB |
Output is correct |
25 |
Correct |
1078 ms |
90268 KB |
Output is correct |
26 |
Correct |
964 ms |
90328 KB |
Output is correct |
27 |
Correct |
1598 ms |
242912 KB |
Output is correct |
28 |
Correct |
1520 ms |
243060 KB |
Output is correct |
29 |
Correct |
1484 ms |
242904 KB |
Output is correct |
30 |
Correct |
1505 ms |
242956 KB |
Output is correct |
31 |
Correct |
49 ms |
83348 KB |
Output is correct |
32 |
Correct |
120 ms |
93348 KB |
Output is correct |
33 |
Correct |
180 ms |
50016 KB |
Output is correct |
34 |
Correct |
1302 ms |
213732 KB |
Output is correct |
35 |
Correct |
46 ms |
36036 KB |
Output is correct |
36 |
Correct |
170 ms |
47364 KB |
Output is correct |
37 |
Correct |
381 ms |
61672 KB |
Output is correct |
38 |
Correct |
640 ms |
137844 KB |
Output is correct |
39 |
Correct |
973 ms |
158052 KB |
Output is correct |
40 |
Correct |
1289 ms |
178036 KB |
Output is correct |
41 |
Correct |
1546 ms |
199032 KB |
Output is correct |
42 |
Correct |
1900 ms |
219516 KB |
Output is correct |
43 |
Correct |
48 ms |
83308 KB |
Output is correct |
44 |
Correct |
47 ms |
83236 KB |
Output is correct |
45 |
Correct |
51 ms |
83304 KB |
Output is correct |
46 |
Correct |
21 ms |
33100 KB |
Output is correct |
47 |
Correct |
22 ms |
33100 KB |
Output is correct |
48 |
Correct |
47 ms |
83200 KB |
Output is correct |
49 |
Correct |
46 ms |
83268 KB |
Output is correct |
50 |
Correct |
47 ms |
83292 KB |
Output is correct |
51 |
Correct |
50 ms |
83204 KB |
Output is correct |
52 |
Correct |
22 ms |
33100 KB |
Output is correct |
53 |
Correct |
49 ms |
83268 KB |
Output is correct |
54 |
Correct |
26 ms |
33720 KB |
Output is correct |
55 |
Correct |
25 ms |
33996 KB |
Output is correct |
56 |
Correct |
613 ms |
153596 KB |
Output is correct |
57 |
Correct |
1040 ms |
185684 KB |
Output is correct |
58 |
Correct |
930 ms |
185684 KB |
Output is correct |
59 |
Correct |
20 ms |
33100 KB |
Output is correct |
60 |
Correct |
47 ms |
83268 KB |
Output is correct |
61 |
Correct |
22 ms |
33108 KB |
Output is correct |
62 |
Correct |
1321 ms |
243144 KB |
Output is correct |
63 |
Correct |
1337 ms |
242940 KB |
Output is correct |
64 |
Correct |
1255 ms |
242364 KB |
Output is correct |
65 |
Correct |
27 ms |
34252 KB |
Output is correct |
66 |
Correct |
36 ms |
35392 KB |
Output is correct |
67 |
Correct |
673 ms |
153336 KB |
Output is correct |
68 |
Correct |
1055 ms |
188500 KB |
Output is correct |
69 |
Correct |
1586 ms |
223276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
33100 KB |
Output is correct |
2 |
Correct |
46 ms |
83268 KB |
Output is correct |
3 |
Correct |
20 ms |
33100 KB |
Output is correct |
4 |
Correct |
47 ms |
83292 KB |
Output is correct |
5 |
Correct |
47 ms |
83228 KB |
Output is correct |
6 |
Correct |
20 ms |
33160 KB |
Output is correct |
7 |
Correct |
21 ms |
33120 KB |
Output is correct |
8 |
Correct |
21 ms |
33164 KB |
Output is correct |
9 |
Correct |
635 ms |
163192 KB |
Output is correct |
10 |
Correct |
79 ms |
91460 KB |
Output is correct |
11 |
Correct |
253 ms |
126548 KB |
Output is correct |
12 |
Correct |
96 ms |
95556 KB |
Output is correct |
13 |
Correct |
97 ms |
45756 KB |
Output is correct |
14 |
Correct |
23 ms |
33484 KB |
Output is correct |
15 |
Correct |
26 ms |
33816 KB |
Output is correct |
16 |
Correct |
564 ms |
163144 KB |
Output is correct |
17 |
Correct |
1423 ms |
243104 KB |
Output is correct |
18 |
Correct |
1330 ms |
243160 KB |
Output is correct |
19 |
Correct |
1395 ms |
213660 KB |
Output is correct |
20 |
Correct |
1565 ms |
222512 KB |
Output is correct |
21 |
Correct |
1344 ms |
218112 KB |
Output is correct |
22 |
Correct |
49 ms |
83232 KB |
Output is correct |
23 |
Correct |
247 ms |
105688 KB |
Output is correct |
24 |
Correct |
70 ms |
38852 KB |
Output is correct |
25 |
Correct |
242 ms |
53392 KB |
Output is correct |
26 |
Correct |
469 ms |
67800 KB |
Output is correct |
27 |
Correct |
784 ms |
153284 KB |
Output is correct |
28 |
Correct |
1079 ms |
170856 KB |
Output is correct |
29 |
Correct |
1330 ms |
188276 KB |
Output is correct |
30 |
Correct |
1572 ms |
205744 KB |
Output is correct |
31 |
Correct |
1820 ms |
223328 KB |
Output is correct |
32 |
Correct |
1468 ms |
225348 KB |
Output is correct |
33 |
Correct |
1352 ms |
243144 KB |
Output is correct |
34 |
Correct |
28 ms |
34520 KB |
Output is correct |
35 |
Correct |
41 ms |
35648 KB |
Output is correct |
36 |
Correct |
643 ms |
153348 KB |
Output is correct |
37 |
Correct |
946 ms |
188808 KB |
Output is correct |
38 |
Correct |
1409 ms |
223488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
33100 KB |
Output is correct |
2 |
Correct |
46 ms |
83268 KB |
Output is correct |
3 |
Correct |
20 ms |
33100 KB |
Output is correct |
4 |
Correct |
47 ms |
83292 KB |
Output is correct |
5 |
Correct |
47 ms |
83228 KB |
Output is correct |
6 |
Correct |
20 ms |
33160 KB |
Output is correct |
7 |
Correct |
21 ms |
33120 KB |
Output is correct |
8 |
Correct |
21 ms |
33164 KB |
Output is correct |
9 |
Correct |
635 ms |
163192 KB |
Output is correct |
10 |
Correct |
79 ms |
91460 KB |
Output is correct |
11 |
Correct |
253 ms |
126548 KB |
Output is correct |
12 |
Correct |
96 ms |
95556 KB |
Output is correct |
13 |
Correct |
97 ms |
45756 KB |
Output is correct |
14 |
Correct |
23 ms |
33484 KB |
Output is correct |
15 |
Correct |
26 ms |
33816 KB |
Output is correct |
16 |
Correct |
564 ms |
163144 KB |
Output is correct |
17 |
Correct |
45 ms |
83232 KB |
Output is correct |
18 |
Correct |
51 ms |
83288 KB |
Output is correct |
19 |
Correct |
55 ms |
83212 KB |
Output is correct |
20 |
Correct |
48 ms |
83276 KB |
Output is correct |
21 |
Correct |
20 ms |
33228 KB |
Output is correct |
22 |
Correct |
44 ms |
83292 KB |
Output is correct |
23 |
Correct |
1337 ms |
214160 KB |
Output is correct |
24 |
Correct |
44 ms |
83272 KB |
Output is correct |
25 |
Correct |
50 ms |
84108 KB |
Output is correct |
26 |
Correct |
25 ms |
33968 KB |
Output is correct |
27 |
Correct |
29 ms |
34368 KB |
Output is correct |
28 |
Correct |
477 ms |
135612 KB |
Output is correct |
29 |
Correct |
710 ms |
161780 KB |
Output is correct |
30 |
Correct |
1078 ms |
187900 KB |
Output is correct |
31 |
Correct |
1336 ms |
214096 KB |
Output is correct |
32 |
Correct |
47 ms |
83192 KB |
Output is correct |
33 |
Correct |
44 ms |
83248 KB |
Output is correct |
34 |
Correct |
45 ms |
83204 KB |
Output is correct |
35 |
Correct |
21 ms |
33084 KB |
Output is correct |
36 |
Correct |
20 ms |
33100 KB |
Output is correct |
37 |
Correct |
50 ms |
83304 KB |
Output is correct |
38 |
Correct |
47 ms |
83232 KB |
Output is correct |
39 |
Correct |
48 ms |
83300 KB |
Output is correct |
40 |
Correct |
47 ms |
83396 KB |
Output is correct |
41 |
Correct |
21 ms |
33100 KB |
Output is correct |
42 |
Correct |
49 ms |
83276 KB |
Output is correct |
43 |
Correct |
26 ms |
33740 KB |
Output is correct |
44 |
Correct |
30 ms |
33996 KB |
Output is correct |
45 |
Correct |
571 ms |
153624 KB |
Output is correct |
46 |
Correct |
925 ms |
185824 KB |
Output is correct |
47 |
Correct |
916 ms |
185664 KB |
Output is correct |
48 |
Correct |
55 ms |
83240 KB |
Output is correct |
49 |
Correct |
45 ms |
83204 KB |
Output is correct |
50 |
Correct |
46 ms |
83272 KB |
Output is correct |
51 |
Correct |
48 ms |
83320 KB |
Output is correct |
52 |
Correct |
48 ms |
83324 KB |
Output is correct |
53 |
Correct |
52 ms |
83316 KB |
Output is correct |
54 |
Correct |
55 ms |
83200 KB |
Output is correct |
55 |
Correct |
1487 ms |
214596 KB |
Output is correct |
56 |
Correct |
48 ms |
83324 KB |
Output is correct |
57 |
Correct |
62 ms |
84484 KB |
Output is correct |
58 |
Correct |
77 ms |
87364 KB |
Output is correct |
59 |
Correct |
48 ms |
36108 KB |
Output is correct |
60 |
Correct |
645 ms |
151944 KB |
Output is correct |
61 |
Correct |
888 ms |
172396 KB |
Output is correct |
62 |
Correct |
1147 ms |
191708 KB |
Output is correct |
63 |
Correct |
1473 ms |
214616 KB |
Output is correct |
64 |
Correct |
23 ms |
33100 KB |
Output is correct |
65 |
Correct |
52 ms |
83256 KB |
Output is correct |
66 |
Correct |
20 ms |
33100 KB |
Output is correct |
67 |
Correct |
1404 ms |
243028 KB |
Output is correct |
68 |
Correct |
1455 ms |
242984 KB |
Output is correct |
69 |
Correct |
1486 ms |
242192 KB |
Output is correct |
70 |
Correct |
28 ms |
34252 KB |
Output is correct |
71 |
Correct |
37 ms |
35380 KB |
Output is correct |
72 |
Correct |
592 ms |
153332 KB |
Output is correct |
73 |
Correct |
1042 ms |
188572 KB |
Output is correct |
74 |
Correct |
1343 ms |
223304 KB |
Output is correct |
75 |
Correct |
1421 ms |
225340 KB |
Output is correct |
76 |
Correct |
1334 ms |
243000 KB |
Output is correct |
77 |
Correct |
34 ms |
34572 KB |
Output is correct |
78 |
Correct |
46 ms |
35672 KB |
Output is correct |
79 |
Correct |
685 ms |
153364 KB |
Output is correct |
80 |
Correct |
995 ms |
188652 KB |
Output is correct |
81 |
Correct |
1344 ms |
223588 KB |
Output is correct |
82 |
Correct |
47 ms |
83264 KB |
Output is correct |
83 |
Correct |
53 ms |
83276 KB |
Output is correct |
84 |
Correct |
23 ms |
33176 KB |
Output is correct |
85 |
Correct |
1275 ms |
213732 KB |
Output is correct |
86 |
Correct |
1331 ms |
213796 KB |
Output is correct |
87 |
Correct |
1369 ms |
213780 KB |
Output is correct |
88 |
Correct |
1084 ms |
219012 KB |
Output is correct |
89 |
Correct |
596 ms |
66828 KB |
Output is correct |
90 |
Correct |
1078 ms |
90268 KB |
Output is correct |
91 |
Correct |
964 ms |
90328 KB |
Output is correct |
92 |
Correct |
1598 ms |
242912 KB |
Output is correct |
93 |
Correct |
1520 ms |
243060 KB |
Output is correct |
94 |
Correct |
1484 ms |
242904 KB |
Output is correct |
95 |
Correct |
1505 ms |
242956 KB |
Output is correct |
96 |
Correct |
49 ms |
83348 KB |
Output is correct |
97 |
Correct |
120 ms |
93348 KB |
Output is correct |
98 |
Correct |
180 ms |
50016 KB |
Output is correct |
99 |
Correct |
1302 ms |
213732 KB |
Output is correct |
100 |
Correct |
46 ms |
36036 KB |
Output is correct |
101 |
Correct |
170 ms |
47364 KB |
Output is correct |
102 |
Correct |
381 ms |
61672 KB |
Output is correct |
103 |
Correct |
640 ms |
137844 KB |
Output is correct |
104 |
Correct |
973 ms |
158052 KB |
Output is correct |
105 |
Correct |
1289 ms |
178036 KB |
Output is correct |
106 |
Correct |
1546 ms |
199032 KB |
Output is correct |
107 |
Correct |
1900 ms |
219516 KB |
Output is correct |
108 |
Correct |
48 ms |
83308 KB |
Output is correct |
109 |
Correct |
47 ms |
83236 KB |
Output is correct |
110 |
Correct |
51 ms |
83304 KB |
Output is correct |
111 |
Correct |
21 ms |
33100 KB |
Output is correct |
112 |
Correct |
22 ms |
33100 KB |
Output is correct |
113 |
Correct |
47 ms |
83200 KB |
Output is correct |
114 |
Correct |
46 ms |
83268 KB |
Output is correct |
115 |
Correct |
47 ms |
83292 KB |
Output is correct |
116 |
Correct |
50 ms |
83204 KB |
Output is correct |
117 |
Correct |
22 ms |
33100 KB |
Output is correct |
118 |
Correct |
49 ms |
83268 KB |
Output is correct |
119 |
Correct |
26 ms |
33720 KB |
Output is correct |
120 |
Correct |
25 ms |
33996 KB |
Output is correct |
121 |
Correct |
613 ms |
153596 KB |
Output is correct |
122 |
Correct |
1040 ms |
185684 KB |
Output is correct |
123 |
Correct |
930 ms |
185684 KB |
Output is correct |
124 |
Correct |
20 ms |
33100 KB |
Output is correct |
125 |
Correct |
47 ms |
83268 KB |
Output is correct |
126 |
Correct |
22 ms |
33108 KB |
Output is correct |
127 |
Correct |
1321 ms |
243144 KB |
Output is correct |
128 |
Correct |
1337 ms |
242940 KB |
Output is correct |
129 |
Correct |
1255 ms |
242364 KB |
Output is correct |
130 |
Correct |
27 ms |
34252 KB |
Output is correct |
131 |
Correct |
36 ms |
35392 KB |
Output is correct |
132 |
Correct |
673 ms |
153336 KB |
Output is correct |
133 |
Correct |
1055 ms |
188500 KB |
Output is correct |
134 |
Correct |
1586 ms |
223276 KB |
Output is correct |
135 |
Correct |
1423 ms |
243104 KB |
Output is correct |
136 |
Correct |
1330 ms |
243160 KB |
Output is correct |
137 |
Correct |
1395 ms |
213660 KB |
Output is correct |
138 |
Correct |
1565 ms |
222512 KB |
Output is correct |
139 |
Correct |
1344 ms |
218112 KB |
Output is correct |
140 |
Correct |
49 ms |
83232 KB |
Output is correct |
141 |
Correct |
247 ms |
105688 KB |
Output is correct |
142 |
Correct |
70 ms |
38852 KB |
Output is correct |
143 |
Correct |
242 ms |
53392 KB |
Output is correct |
144 |
Correct |
469 ms |
67800 KB |
Output is correct |
145 |
Correct |
784 ms |
153284 KB |
Output is correct |
146 |
Correct |
1079 ms |
170856 KB |
Output is correct |
147 |
Correct |
1330 ms |
188276 KB |
Output is correct |
148 |
Correct |
1572 ms |
205744 KB |
Output is correct |
149 |
Correct |
1820 ms |
223328 KB |
Output is correct |
150 |
Correct |
1468 ms |
225348 KB |
Output is correct |
151 |
Correct |
1352 ms |
243144 KB |
Output is correct |
152 |
Correct |
28 ms |
34520 KB |
Output is correct |
153 |
Correct |
41 ms |
35648 KB |
Output is correct |
154 |
Correct |
643 ms |
153348 KB |
Output is correct |
155 |
Correct |
946 ms |
188808 KB |
Output is correct |
156 |
Correct |
1409 ms |
223488 KB |
Output is correct |
157 |
Correct |
48 ms |
83316 KB |
Output is correct |
158 |
Correct |
20 ms |
33100 KB |
Output is correct |
159 |
Correct |
46 ms |
83236 KB |
Output is correct |
160 |
Correct |
48 ms |
83268 KB |
Output is correct |
161 |
Correct |
1590 ms |
215668 KB |
Output is correct |
162 |
Correct |
1335 ms |
213744 KB |
Output is correct |
163 |
Correct |
1332 ms |
214572 KB |
Output is correct |
164 |
Correct |
1296 ms |
214568 KB |
Output is correct |
165 |
Correct |
1372 ms |
215060 KB |
Output is correct |
166 |
Correct |
1444 ms |
215524 KB |
Output is correct |
167 |
Execution timed out |
3579 ms |
583452 KB |
Time limit exceeded |
168 |
Halted |
0 ms |
0 KB |
- |