oj.uz

답안 #622477

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
622477 2022-08-04T10:10:05 Z Koosha_mv 분수 공원 (IOI21_parks) C++17
15 / 100
 1789 ms 132172 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));
		}
	}
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 18 ms 39456 KB Output is correct
3 Correct 18 ms 39380 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 18 ms 39384 KB Output is correct
6 Correct 22 ms 39428 KB Output is correct
7 Correct 19 ms 39380 KB Output is correct
8 Correct 19 ms 39380 KB Output is correct
9 Correct 639 ms 84512 KB Output is correct
10 Correct 47 ms 44132 KB Output is correct
11 Correct 187 ms 63764 KB Output is correct
12 Correct 59 ms 46496 KB Output is correct
13 Correct 148 ms 58024 KB Output is correct
14 Correct 23 ms 39892 KB Output is correct
15 Correct 25 ms 40228 KB Output is correct
16 Correct 579 ms 84428 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 18 ms 39456 KB Output is correct
3 Correct 18 ms 39380 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 18 ms 39384 KB Output is correct
6 Correct 22 ms 39428 KB Output is correct
7 Correct 19 ms 39380 KB Output is correct
8 Correct 19 ms 39380 KB Output is correct
9 Correct 639 ms 84512 KB Output is correct
10 Correct 47 ms 44132 KB Output is correct
11 Correct 187 ms 63764 KB Output is correct
12 Correct 59 ms 46496 KB Output is correct
13 Correct 148 ms 58024 KB Output is correct
14 Correct 23 ms 39892 KB Output is correct
15 Correct 25 ms 40228 KB Output is correct
16 Correct 579 ms 84428 KB Output is correct
17 Correct 19 ms 39432 KB Output is correct
18 Correct 19 ms 39464 KB Output is correct
19 Correct 19 ms 39424 KB Output is correct
20 Correct 19 ms 39380 KB Output is correct
21 Correct 22 ms 39416 KB Output is correct
22 Correct 19 ms 39380 KB Output is correct
23 Correct 1789 ms 132172 KB Output is correct
24 Correct 20 ms 39388 KB Output is correct
25 Correct 29 ms 39940 KB Output is correct
26 Correct 34 ms 40844 KB Output is correct
27 Correct 39 ms 41164 KB Output is correct
28 Correct 583 ms 76520 KB Output is correct
29 Correct 943 ms 95120 KB Output is correct
30 Correct 1295 ms 113568 KB Output is correct
31 Correct 1684 ms 132064 KB Output is correct
32 Correct 20 ms 39380 KB Output is correct
33 Correct 20 ms 39380 KB Output is correct
34 Correct 19 ms 39412 KB Output is correct
35 Correct 19 ms 39380 KB Output is correct
36 Correct 22 ms 39452 KB Output is correct
37 Correct 20 ms 39360 KB Output is correct
38 Correct 19 ms 39380 KB Output is correct
39 Correct 20 ms 39380 KB Output is correct
40 Correct 20 ms 39428 KB Output is correct
41 Correct 19 ms 39380 KB Output is correct
42 Correct 20 ms 39380 KB Output is correct
43 Correct 24 ms 40184 KB Output is correct
44 Correct 27 ms 40532 KB Output is correct
45 Correct 586 ms 78308 KB Output is correct
46 Correct 957 ms 95652 KB Output is correct
47 Correct 908 ms 95584 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 18 ms 39456 KB Output is correct
3 Correct 18 ms 39380 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 18 ms 39384 KB Output is correct
6 Correct 22 ms 39428 KB Output is correct
7 Correct 19 ms 39380 KB Output is correct
8 Correct 19 ms 39380 KB Output is correct
9 Correct 639 ms 84512 KB Output is correct
10 Correct 47 ms 44132 KB Output is correct
11 Correct 187 ms 63764 KB Output is correct
12 Correct 59 ms 46496 KB Output is correct
13 Correct 148 ms 58024 KB Output is correct
14 Correct 23 ms 39892 KB Output is correct
15 Correct 25 ms 40228 KB Output is correct
16 Correct 579 ms 84428 KB Output is correct
17 Correct 19 ms 39432 KB Output is correct
18 Correct 19 ms 39464 KB Output is correct
19 Correct 19 ms 39424 KB Output is correct
20 Correct 19 ms 39380 KB Output is correct
21 Correct 22 ms 39416 KB Output is correct
22 Correct 19 ms 39380 KB Output is correct
23 Correct 1789 ms 132172 KB Output is correct
24 Correct 20 ms 39388 KB Output is correct
25 Correct 29 ms 39940 KB Output is correct
26 Correct 34 ms 40844 KB Output is correct
27 Correct 39 ms 41164 KB Output is correct
28 Correct 583 ms 76520 KB Output is correct
29 Correct 943 ms 95120 KB Output is correct
30 Correct 1295 ms 113568 KB Output is correct
31 Correct 1684 ms 132064 KB Output is correct
32 Correct 20 ms 39380 KB Output is correct
33 Correct 20 ms 39380 KB Output is correct
34 Correct 19 ms 39412 KB Output is correct
35 Correct 19 ms 39380 KB Output is correct
36 Correct 22 ms 39452 KB Output is correct
37 Correct 20 ms 39360 KB Output is correct
38 Correct 19 ms 39380 KB Output is correct
39 Correct 20 ms 39380 KB Output is correct
40 Correct 20 ms 39428 KB Output is correct
41 Correct 19 ms 39380 KB Output is correct
42 Correct 20 ms 39380 KB Output is correct
43 Correct 24 ms 40184 KB Output is correct
44 Correct 27 ms 40532 KB Output is correct
45 Correct 586 ms 78308 KB Output is correct
46 Correct 957 ms 95652 KB Output is correct
47 Correct 908 ms 95584 KB Output is correct
48 Correct 19 ms 39380 KB Output is correct
49 Correct 19 ms 39388 KB Output is correct
50 Correct 19 ms 39516 KB Output is correct
51 Incorrect 20 ms 39400 KB a[1] = 0 is not an odd integer
52 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 18 ms 39456 KB Output is correct
3 Correct 18 ms 39380 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 18 ms 39384 KB Output is correct
6 Correct 22 ms 39428 KB Output is correct
7 Correct 19 ms 39380 KB Output is correct
8 Correct 19 ms 39380 KB Output is correct
9 Correct 639 ms 84512 KB Output is correct
10 Correct 47 ms 44132 KB Output is correct
11 Correct 187 ms 63764 KB Output is correct
12 Correct 59 ms 46496 KB Output is correct
13 Correct 148 ms 58024 KB Output is correct
14 Correct 23 ms 39892 KB Output is correct
15 Correct 25 ms 40228 KB Output is correct
16 Correct 579 ms 84428 KB Output is correct
17 Correct 20 ms 39380 KB Output is correct
18 Correct 22 ms 39380 KB Output is correct
19 Correct 19 ms 39380 KB Output is correct
20 Correct 837 ms 106896 KB Output is correct
21 Correct 1029 ms 109232 KB Output is correct
22 Correct 898 ms 109156 KB Output is correct
23 Correct 974 ms 117540 KB Output is correct
24 Correct 176 ms 55176 KB Output is correct
25 Correct 1197 ms 124096 KB Output is correct
26 Correct 1188 ms 124032 KB Output is correct
27 Correct 1245 ms 130512 KB Output is correct
28 Correct 1224 ms 130408 KB Output is correct
29 Correct 1230 ms 130452 KB Output is correct
30 Correct 1289 ms 130388 KB Output is correct
31 Correct 20 ms 39380 KB Output is correct
32 Incorrect 68 ms 45056 KB a[12] = 0 is not an odd integer
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 18 ms 39456 KB Output is correct
3 Correct 18 ms 39380 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 18 ms 39384 KB Output is correct
6 Correct 22 ms 39428 KB Output is correct
7 Correct 19 ms 39380 KB Output is correct
8 Correct 19 ms 39380 KB Output is correct
9 Correct 639 ms 84512 KB Output is correct
10 Correct 47 ms 44132 KB Output is correct
11 Correct 187 ms 63764 KB Output is correct
12 Correct 59 ms 46496 KB Output is correct
13 Correct 148 ms 58024 KB Output is correct
14 Correct 23 ms 39892 KB Output is correct
15 Correct 25 ms 40228 KB Output is correct
16 Correct 579 ms 84428 KB Output is correct
17 Correct 1280 ms 129088 KB Output is correct
18 Incorrect 1239 ms 129348 KB a[11866] = 0 is not an odd integer
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39380 KB Output is correct
2 Correct 18 ms 39456 KB Output is correct
3 Correct 18 ms 39380 KB Output is correct
4 Correct 18 ms 39436 KB Output is correct
5 Correct 18 ms 39384 KB Output is correct
6 Correct 22 ms 39428 KB Output is correct
7 Correct 19 ms 39380 KB Output is correct
8 Correct 19 ms 39380 KB Output is correct
9 Correct 639 ms 84512 KB Output is correct
10 Correct 47 ms 44132 KB Output is correct
11 Correct 187 ms 63764 KB Output is correct
12 Correct 59 ms 46496 KB Output is correct
13 Correct 148 ms 58024 KB Output is correct
14 Correct 23 ms 39892 KB Output is correct
15 Correct 25 ms 40228 KB Output is correct
16 Correct 579 ms 84428 KB Output is correct
17 Correct 19 ms 39432 KB Output is correct
18 Correct 19 ms 39464 KB Output is correct
19 Correct 19 ms 39424 KB Output is correct
20 Correct 19 ms 39380 KB Output is correct
21 Correct 22 ms 39416 KB Output is correct
22 Correct 19 ms 39380 KB Output is correct
23 Correct 1789 ms 132172 KB Output is correct
24 Correct 20 ms 39388 KB Output is correct
25 Correct 29 ms 39940 KB Output is correct
26 Correct 34 ms 40844 KB Output is correct
27 Correct 39 ms 41164 KB Output is correct
28 Correct 583 ms 76520 KB Output is correct
29 Correct 943 ms 95120 KB Output is correct
30 Correct 1295 ms 113568 KB Output is correct
31 Correct 1684 ms 132064 KB Output is correct
32 Correct 20 ms 39380 KB Output is correct
33 Correct 20 ms 39380 KB Output is correct
34 Correct 19 ms 39412 KB Output is correct
35 Correct 19 ms 39380 KB Output is correct
36 Correct 22 ms 39452 KB Output is correct
37 Correct 20 ms 39360 KB Output is correct
38 Correct 19 ms 39380 KB Output is correct
39 Correct 20 ms 39380 KB Output is correct
40 Correct 20 ms 39428 KB Output is correct
41 Correct 19 ms 39380 KB Output is correct
42 Correct 20 ms 39380 KB Output is correct
43 Correct 24 ms 40184 KB Output is correct
44 Correct 27 ms 40532 KB Output is correct
45 Correct 586 ms 78308 KB Output is correct
46 Correct 957 ms 95652 KB Output is correct
47 Correct 908 ms 95584 KB Output is correct
48 Correct 19 ms 39380 KB Output is correct
49 Correct 19 ms 39388 KB Output is correct
50 Correct 19 ms 39516 KB Output is correct
51 Incorrect 20 ms 39400 KB a[1] = 0 is not an odd integer
52 Halted 0 ms 0 KB -