Submission #622455

#	Time	Username	Problem	Language	Result	Execution time	Memory
622455		Koosha_mv	Fountain Parks (IOI21_parks)	C++17	5 / 100	1082 ms	101384 KiB

parks

#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=2e5+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(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));
		}
	}
	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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30