oj.uz

답안 #622471

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
622471 2022-08-04T10:01:55 Z Koosha_mv 분수 공원 (IOI21_parks) C++17
5 / 100
 684 ms 191216 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> 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)])){
			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(a[u]+2==a[v]){
			del(a[u]+1,a[v]+1,mp(u,v));
			del(a[u]+1,a[v]-1,mp(u,v));
		}
		else{
			del(a[u]+1,a[v]+1,mp(u,v));
			del(a[u]-1,a[v]+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;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 20564 KB Output is correct
2 Correct 12 ms 20692 KB Output is correct
3 Correct 11 ms 20564 KB Output is correct
4 Correct 10 ms 20564 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20620 KB Output is correct
7 Correct 10 ms 20564 KB Output is correct
8 Correct 10 ms 20564 KB Output is correct
9 Correct 477 ms 61828 KB Output is correct
10 Correct 36 ms 25072 KB Output is correct
11 Correct 156 ms 42852 KB Output is correct
12 Correct 45 ms 27088 KB Output is correct
13 Correct 112 ms 37408 KB Output is correct
14 Correct 13 ms 20960 KB Output is correct
15 Correct 18 ms 21316 KB Output is correct
16 Correct 490 ms 61816 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 20564 KB Output is correct
2 Correct 12 ms 20692 KB Output is correct
3 Correct 11 ms 20564 KB Output is correct
4 Correct 10 ms 20564 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20620 KB Output is correct
7 Correct 10 ms 20564 KB Output is correct
8 Correct 10 ms 20564 KB Output is correct
9 Correct 477 ms 61828 KB Output is correct
10 Correct 36 ms 25072 KB Output is correct
11 Correct 156 ms 42852 KB Output is correct
12 Correct 45 ms 27088 KB Output is correct
13 Correct 112 ms 37408 KB Output is correct
14 Correct 13 ms 20960 KB Output is correct
15 Correct 18 ms 21316 KB Output is correct
16 Correct 490 ms 61816 KB Output is correct
17 Runtime error 28 ms 41636 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 20564 KB Output is correct
2 Correct 12 ms 20692 KB Output is correct
3 Correct 11 ms 20564 KB Output is correct
4 Correct 10 ms 20564 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20620 KB Output is correct
7 Correct 10 ms 20564 KB Output is correct
8 Correct 10 ms 20564 KB Output is correct
9 Correct 477 ms 61828 KB Output is correct
10 Correct 36 ms 25072 KB Output is correct
11 Correct 156 ms 42852 KB Output is correct
12 Correct 45 ms 27088 KB Output is correct
13 Correct 112 ms 37408 KB Output is correct
14 Correct 13 ms 20960 KB Output is correct
15 Correct 18 ms 21316 KB Output is correct
16 Correct 490 ms 61816 KB Output is correct
17 Runtime error 28 ms 41636 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 20564 KB Output is correct
2 Correct 12 ms 20692 KB Output is correct
3 Correct 11 ms 20564 KB Output is correct
4 Correct 10 ms 20564 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20620 KB Output is correct
7 Correct 10 ms 20564 KB Output is correct
8 Correct 10 ms 20564 KB Output is correct
9 Correct 477 ms 61828 KB Output is correct
10 Correct 36 ms 25072 KB Output is correct
11 Correct 156 ms 42852 KB Output is correct
12 Correct 45 ms 27088 KB Output is correct
13 Correct 112 ms 37408 KB Output is correct
14 Correct 13 ms 20960 KB Output is correct
15 Correct 18 ms 21316 KB Output is correct
16 Correct 490 ms 61816 KB Output is correct
17 Correct 10 ms 20564 KB Output is correct
18 Correct 10 ms 20564 KB Output is correct
19 Runtime error 26 ms 41748 KB Execution killed with signal 6
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 20564 KB Output is correct
2 Correct 12 ms 20692 KB Output is correct
3 Correct 11 ms 20564 KB Output is correct
4 Correct 10 ms 20564 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20620 KB Output is correct
7 Correct 10 ms 20564 KB Output is correct
8 Correct 10 ms 20564 KB Output is correct
9 Correct 477 ms 61828 KB Output is correct
10 Correct 36 ms 25072 KB Output is correct
11 Correct 156 ms 42852 KB Output is correct
12 Correct 45 ms 27088 KB Output is correct
13 Correct 112 ms 37408 KB Output is correct
14 Correct 13 ms 20960 KB Output is correct
15 Correct 18 ms 21316 KB Output is correct
16 Correct 490 ms 61816 KB Output is correct
17 Runtime error 684 ms 191216 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 20564 KB Output is correct
2 Correct 12 ms 20692 KB Output is correct
3 Correct 11 ms 20564 KB Output is correct
4 Correct 10 ms 20564 KB Output is correct
5 Correct 10 ms 20564 KB Output is correct
6 Correct 11 ms 20620 KB Output is correct
7 Correct 10 ms 20564 KB Output is correct
8 Correct 10 ms 20564 KB Output is correct
9 Correct 477 ms 61828 KB Output is correct
10 Correct 36 ms 25072 KB Output is correct
11 Correct 156 ms 42852 KB Output is correct
12 Correct 45 ms 27088 KB Output is correct
13 Correct 112 ms 37408 KB Output is correct
14 Correct 13 ms 20960 KB Output is correct
15 Correct 18 ms 21316 KB Output is correct
16 Correct 490 ms 61816 KB Output is correct
17 Runtime error 28 ms 41636 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -