oj.uz

Submission #622484

# Submission time Handle Problem Language Result Execution time Memory
622484 2022-08-04T10:18:47 Z Koosha_mv Fountain Parks (IOI21_parks) C++17
35 / 100
 1842 ms 130664 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=4e5+99;

int n,a[N],b[N],f[N];
queue<pair<int,int>> q;
map<int,int> ok[N],mark[N];
map<pair<int,int>,vector<pair<int,int>>> sq;
map<pair<int,int>,pair<int,int>> tn;

int getpar(int u){
	if(f[u]<0) return u;
	return f[u]=getpar(f[u]);
}
int merge(int u,int v){
	u=getpar(u),v=getpar(v);
	if(u==v) return 0;
	if(f[u]>f[v]) swap(u,v);
	f[u]+=f[v];
	f[v]=u;
	return 1;
}
void del(int x,int y,pair<int,int> p){
	f(i,0,sz(sq[mp(x,y)])){
		if(sq[mp(x,y)][i]==p){
			sq[mp(x,y)].erase(sq[mp(x,y)].begin()+i);
			break ;
		}
		if(i+1==sz(sq[mp(x,y)])){
			cout<<x<<" "<<y<<" + "<<p.F<<" "<<p.S<<endl;
			assert(0);
		}
	}
	if(sz(sq[mp(x,y)])==1){
		tn[sq[mp(x,y)][0]]=mp(x,y);
		q.push(sq[mp(x,y)][0]);
	}
}
int construct_roads(vector<int> _a,vector<int> _b) {
	fill(f,f+N,-1);
	f(i,0,sz(_a)) a[i+1]=_a[i];
	f(i,0,sz(_b)) b[i+1]=_b[i];
	n=_a.size();
	f(i,1,n+1){
		mark[a[i]][b[i]]=i;
	}
	f(i,1,n+1){
		if(mark[a[i]+2].count(b[i])){
			int j=mark[a[i]+2][b[i]];
			sq[{a[i]+1,b[i]+1}].pb({i,j});
			sq[{a[i]+1,b[i]-1}].pb({i,j});
		}
		if(mark[a[i]].count(b[i]+2)){
			int j=mark[a[i]][b[i]+2];
			sq[{a[i]+1,b[i]+1}].pb({i,j});
			sq[{a[i]-1,b[i]+1}].pb({i,j});	
		}
	}
	for(auto [p,v] : sq){
		if(v.size()==1){
			tn[v[0]]=p;
			q.push(v[0]);
		}
	}
	while(q.size()){
		int u=q.front().F,v=q.front().S;
		q.pop();
		if(ok[u][v]) continue ;
		ok[u][v]=1;
		//cout<<u<<" -> "<<v<<endl;
		if(a[u]+2==a[v]){
			del(a[u]+1,b[u]+1,mp(u,v));
			del(a[u]+1,b[u]-1,mp(u,v));
		}
		else{
			del(a[u]+1,b[u]+1,mp(u,v));
			del(a[u]-1,b[u]+1,mp(u,v));
		}
	}
	f(i,1,n+1){
		if(mark[a[i]-2].count(b[i]) && mark[a[i]].count(b[i]-2) && mark[a[i]+2].count(b[i]) && mark[a[i]].count(b[i]+2)){
			int A=mark[a[i]-2][b[i]];
			int B=mark[a[i]][b[i]+2];
			int C=mark[a[i]+2][b[i]];
			int D=mark[a[i]][b[i]-2];
			tn[mp(A,i)]=mp(a[i]-1,b[i]+1);
			tn[mp(i,B)]=mp(a[i]+1,b[i]+1);
			tn[mp(i,C)]=mp(a[i]+1,b[i]-1);
			tn[mp(D,i)]=mp(a[i]-1,b[i]-1);
		}
	}
	vector<int> U,V,A,B;
	f(i,1,n+1){
		if(mark[a[i]+2].count(b[i])){
			int j=mark[a[i]+2][b[i]];
			if(merge(i,j)){
				U.pb(i-1);
				V.pb(j-1);
				A.pb(tn[mp(i,j)].F);
				B.pb(tn[mp(i,j)].S);
			}
		}
		if(mark[a[i]].count(b[i]+2)){
			int j=mark[a[i]][b[i]+2];
			if(merge(i,j)){
				U.pb(i-1);
				V.pb(j-1);
				A.pb(tn[mp(i,j)].F);
				B.pb(tn[mp(i,j)].S);
			}	
		}
	}
	if(f[getpar(1)]!=-n) return 0;
	/*cout<<endl;
	cout<<U.size()<<endl;
	f(i,0,n-1){
		cout<<U[i]<<" "<<V[i]<<" "<<A[i]<<" "<<B[i]<<endl;
	}
	cout<<endl;*/
	build(U,V,A,B);
	return 1;
}
/*
5
2 2
4 2
6 2
6 4
6 6
8 6
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 21 ms 39428 KB Output is correct
3 Correct 21 ms 39420 KB Output is correct
4 Correct 20 ms 39468 KB Output is correct
5 Correct 20 ms 39380 KB Output is correct
6 Correct 19 ms 39372 KB Output is correct
7 Correct 20 ms 39468 KB Output is correct
8 Correct 20 ms 39360 KB Output is correct
9 Correct 607 ms 84484 KB Output is correct
10 Correct 46 ms 44212 KB Output is correct
11 Correct 202 ms 63640 KB Output is correct
12 Correct 59 ms 46520 KB Output is correct
13 Correct 139 ms 57908 KB Output is correct
14 Correct 24 ms 39892 KB Output is correct
15 Correct 26 ms 40300 KB Output is correct
16 Correct 588 ms 84480 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 21 ms 39428 KB Output is correct
3 Correct 21 ms 39420 KB Output is correct
4 Correct 20 ms 39468 KB Output is correct
5 Correct 20 ms 39380 KB Output is correct
6 Correct 19 ms 39372 KB Output is correct
7 Correct 20 ms 39468 KB Output is correct
8 Correct 20 ms 39360 KB Output is correct
9 Correct 607 ms 84484 KB Output is correct
10 Correct 46 ms 44212 KB Output is correct
11 Correct 202 ms 63640 KB Output is correct
12 Correct 59 ms 46520 KB Output is correct
13 Correct 139 ms 57908 KB Output is correct
14 Correct 24 ms 39892 KB Output is correct
15 Correct 26 ms 40300 KB Output is correct
16 Correct 588 ms 84480 KB Output is correct
17 Correct 20 ms 39380 KB Output is correct
18 Correct 20 ms 39464 KB Output is correct
19 Correct 19 ms 39416 KB Output is correct
20 Correct 20 ms 39448 KB Output is correct
21 Correct 20 ms 39360 KB Output is correct
22 Correct 19 ms 39344 KB Output is correct
23 Correct 1744 ms 130416 KB Output is correct
24 Correct 22 ms 39368 KB Output is correct
25 Correct 24 ms 40024 KB Output is correct
26 Correct 28 ms 40720 KB Output is correct
27 Correct 33 ms 41112 KB Output is correct
28 Correct 564 ms 75976 KB Output is correct
29 Correct 985 ms 94060 KB Output is correct
30 Correct 1448 ms 112404 KB Output is correct
31 Correct 1842 ms 130444 KB Output is correct
32 Correct 20 ms 39364 KB Output is correct
33 Correct 21 ms 39320 KB Output is correct
34 Correct 19 ms 39404 KB Output is correct
35 Correct 19 ms 39428 KB Output is correct
36 Correct 18 ms 39416 KB Output is correct
37 Correct 18 ms 39384 KB Output is correct
38 Correct 18 ms 39380 KB Output is correct
39 Correct 23 ms 39380 KB Output is correct
40 Correct 17 ms 39432 KB Output is correct
41 Correct 19 ms 39380 KB Output is correct
42 Correct 20 ms 39380 KB Output is correct
43 Correct 27 ms 40076 KB Output is correct
44 Correct 28 ms 40540 KB Output is correct
45 Correct 590 ms 77352 KB Output is correct
46 Correct 949 ms 94368 KB Output is correct
47 Correct 942 ms 94460 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 21 ms 39428 KB Output is correct
3 Correct 21 ms 39420 KB Output is correct
4 Correct 20 ms 39468 KB Output is correct
5 Correct 20 ms 39380 KB Output is correct
6 Correct 19 ms 39372 KB Output is correct
7 Correct 20 ms 39468 KB Output is correct
8 Correct 20 ms 39360 KB Output is correct
9 Correct 607 ms 84484 KB Output is correct
10 Correct 46 ms 44212 KB Output is correct
11 Correct 202 ms 63640 KB Output is correct
12 Correct 59 ms 46520 KB Output is correct
13 Correct 139 ms 57908 KB Output is correct
14 Correct 24 ms 39892 KB Output is correct
15 Correct 26 ms 40300 KB Output is correct
16 Correct 588 ms 84480 KB Output is correct
17 Correct 20 ms 39380 KB Output is correct
18 Correct 20 ms 39464 KB Output is correct
19 Correct 19 ms 39416 KB Output is correct
20 Correct 20 ms 39448 KB Output is correct
21 Correct 20 ms 39360 KB Output is correct
22 Correct 19 ms 39344 KB Output is correct
23 Correct 1744 ms 130416 KB Output is correct
24 Correct 22 ms 39368 KB Output is correct
25 Correct 24 ms 40024 KB Output is correct
26 Correct 28 ms 40720 KB Output is correct
27 Correct 33 ms 41112 KB Output is correct
28 Correct 564 ms 75976 KB Output is correct
29 Correct 985 ms 94060 KB Output is correct
30 Correct 1448 ms 112404 KB Output is correct
31 Correct 1842 ms 130444 KB Output is correct
32 Correct 20 ms 39364 KB Output is correct
33 Correct 21 ms 39320 KB Output is correct
34 Correct 19 ms 39404 KB Output is correct
35 Correct 19 ms 39428 KB Output is correct
36 Correct 18 ms 39416 KB Output is correct
37 Correct 18 ms 39384 KB Output is correct
38 Correct 18 ms 39380 KB Output is correct
39 Correct 23 ms 39380 KB Output is correct
40 Correct 17 ms 39432 KB Output is correct
41 Correct 19 ms 39380 KB Output is correct
42 Correct 20 ms 39380 KB Output is correct
43 Correct 27 ms 40076 KB Output is correct
44 Correct 28 ms 40540 KB Output is correct
45 Correct 590 ms 77352 KB Output is correct
46 Correct 949 ms 94368 KB Output is correct
47 Correct 942 ms 94460 KB Output is correct
48 Correct 19 ms 39352 KB Output is correct
49 Correct 20 ms 39440 KB Output is correct
50 Correct 19 ms 39348 KB Output is correct
51 Correct 20 ms 39388 KB Output is correct
52 Correct 20 ms 39392 KB Output is correct
53 Correct 20 ms 39456 KB Output is correct
54 Correct 19 ms 39448 KB Output is correct
55 Incorrect 1688 ms 123316 KB Tree @(3, 66613) appears more than once: for edges on positions 564 and 993
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 21 ms 39428 KB Output is correct
3 Correct 21 ms 39420 KB Output is correct
4 Correct 20 ms 39468 KB Output is correct
5 Correct 20 ms 39380 KB Output is correct
6 Correct 19 ms 39372 KB Output is correct
7 Correct 20 ms 39468 KB Output is correct
8 Correct 20 ms 39360 KB Output is correct
9 Correct 607 ms 84484 KB Output is correct
10 Correct 46 ms 44212 KB Output is correct
11 Correct 202 ms 63640 KB Output is correct
12 Correct 59 ms 46520 KB Output is correct
13 Correct 139 ms 57908 KB Output is correct
14 Correct 24 ms 39892 KB Output is correct
15 Correct 26 ms 40300 KB Output is correct
16 Correct 588 ms 84480 KB Output is correct
17 Correct 23 ms 39340 KB Output is correct
18 Correct 19 ms 39380 KB Output is correct
19 Correct 21 ms 39344 KB Output is correct
20 Correct 937 ms 106936 KB Output is correct
21 Correct 1124 ms 106928 KB Output is correct
22 Correct 955 ms 106904 KB Output is correct
23 Correct 1050 ms 115956 KB Output is correct
24 Correct 187 ms 53536 KB Output is correct
25 Correct 1473 ms 122388 KB Output is correct
26 Correct 1287 ms 122376 KB Output is correct
27 Correct 1371 ms 128764 KB Output is correct
28 Correct 1375 ms 128800 KB Output is correct
29 Correct 1429 ms 128952 KB Output is correct
30 Correct 1402 ms 128716 KB Output is correct
31 Correct 22 ms 39400 KB Output is correct
32 Correct 81 ms 44920 KB Output is correct
33 Correct 67 ms 47756 KB Output is correct
34 Correct 1028 ms 109416 KB Output is correct
35 Correct 50 ms 42804 KB Output is correct
36 Correct 253 ms 56116 KB Output is correct
37 Correct 535 ms 72888 KB Output is correct
38 Correct 508 ms 68648 KB Output is correct
39 Correct 791 ms 79488 KB Output is correct
40 Correct 994 ms 90348 KB Output is correct
41 Correct 1248 ms 101272 KB Output is correct
42 Correct 1589 ms 112176 KB Output is correct
43 Correct 19 ms 39412 KB Output is correct
44 Correct 19 ms 39380 KB Output is correct
45 Correct 20 ms 39460 KB Output is correct
46 Correct 23 ms 39380 KB Output is correct
47 Correct 22 ms 39424 KB Output is correct
48 Correct 22 ms 39380 KB Output is correct
49 Correct 18 ms 39380 KB Output is correct
50 Correct 27 ms 39372 KB Output is correct
51 Correct 20 ms 39380 KB Output is correct
52 Correct 20 ms 39456 KB Output is correct
53 Correct 23 ms 39388 KB Output is correct
54 Correct 24 ms 40148 KB Output is correct
55 Correct 33 ms 40524 KB Output is correct
56 Correct 665 ms 78288 KB Output is correct
57 Correct 1048 ms 95644 KB Output is correct
58 Correct 1018 ms 95584 KB Output is correct
59 Correct 25 ms 39380 KB Output is correct
60 Correct 21 ms 39348 KB Output is correct
61 Correct 22 ms 39460 KB Output is correct
62 Correct 1573 ms 130384 KB Output is correct
63 Correct 1524 ms 130400 KB Output is correct
64 Correct 1496 ms 130664 KB Output is correct
65 Correct 32 ms 40788 KB Output is correct
66 Correct 54 ms 42292 KB Output is correct
67 Correct 761 ms 77292 KB Output is correct
68 Correct 1169 ms 96360 KB Output is correct
69 Correct 1640 ms 115220 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 21 ms 39428 KB Output is correct
3 Correct 21 ms 39420 KB Output is correct
4 Correct 20 ms 39468 KB Output is correct
5 Correct 20 ms 39380 KB Output is correct
6 Correct 19 ms 39372 KB Output is correct
7 Correct 20 ms 39468 KB Output is correct
8 Correct 20 ms 39360 KB Output is correct
9 Correct 607 ms 84484 KB Output is correct
10 Correct 46 ms 44212 KB Output is correct
11 Correct 202 ms 63640 KB Output is correct
12 Correct 59 ms 46520 KB Output is correct
13 Correct 139 ms 57908 KB Output is correct
14 Correct 24 ms 39892 KB Output is correct
15 Correct 26 ms 40300 KB Output is correct
16 Correct 588 ms 84480 KB Output is correct
17 Correct 1324 ms 129152 KB Output is correct
18 Correct 1409 ms 129116 KB Output is correct
19 Incorrect 611 ms 99672 KB a[0] = 0 is not an odd integer
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 39380 KB Output is correct
2 Correct 21 ms 39428 KB Output is correct
3 Correct 21 ms 39420 KB Output is correct
4 Correct 20 ms 39468 KB Output is correct
5 Correct 20 ms 39380 KB Output is correct
6 Correct 19 ms 39372 KB Output is correct
7 Correct 20 ms 39468 KB Output is correct
8 Correct 20 ms 39360 KB Output is correct
9 Correct 607 ms 84484 KB Output is correct
10 Correct 46 ms 44212 KB Output is correct
11 Correct 202 ms 63640 KB Output is correct
12 Correct 59 ms 46520 KB Output is correct
13 Correct 139 ms 57908 KB Output is correct
14 Correct 24 ms 39892 KB Output is correct
15 Correct 26 ms 40300 KB Output is correct
16 Correct 588 ms 84480 KB Output is correct
17 Correct 20 ms 39380 KB Output is correct
18 Correct 20 ms 39464 KB Output is correct
19 Correct 19 ms 39416 KB Output is correct
20 Correct 20 ms 39448 KB Output is correct
21 Correct 20 ms 39360 KB Output is correct
22 Correct 19 ms 39344 KB Output is correct
23 Correct 1744 ms 130416 KB Output is correct
24 Correct 22 ms 39368 KB Output is correct
25 Correct 24 ms 40024 KB Output is correct
26 Correct 28 ms 40720 KB Output is correct
27 Correct 33 ms 41112 KB Output is correct
28 Correct 564 ms 75976 KB Output is correct
29 Correct 985 ms 94060 KB Output is correct
30 Correct 1448 ms 112404 KB Output is correct
31 Correct 1842 ms 130444 KB Output is correct
32 Correct 20 ms 39364 KB Output is correct
33 Correct 21 ms 39320 KB Output is correct
34 Correct 19 ms 39404 KB Output is correct
35 Correct 19 ms 39428 KB Output is correct
36 Correct 18 ms 39416 KB Output is correct
37 Correct 18 ms 39384 KB Output is correct
38 Correct 18 ms 39380 KB Output is correct
39 Correct 23 ms 39380 KB Output is correct
40 Correct 17 ms 39432 KB Output is correct
41 Correct 19 ms 39380 KB Output is correct
42 Correct 20 ms 39380 KB Output is correct
43 Correct 27 ms 40076 KB Output is correct
44 Correct 28 ms 40540 KB Output is correct
45 Correct 590 ms 77352 KB Output is correct
46 Correct 949 ms 94368 KB Output is correct
47 Correct 942 ms 94460 KB Output is correct
48 Correct 19 ms 39352 KB Output is correct
49 Correct 20 ms 39440 KB Output is correct
50 Correct 19 ms 39348 KB Output is correct
51 Correct 20 ms 39388 KB Output is correct
52 Correct 20 ms 39392 KB Output is correct
53 Correct 20 ms 39456 KB Output is correct
54 Correct 19 ms 39448 KB Output is correct
55 Incorrect 1688 ms 123316 KB Tree @(3, 66613) appears more than once: for edges on positions 564 and 993
56 Halted 0 ms 0 KB -