Submission #645971

#	Time	Username	Problem	Language	Result	Execution time	Memory
645971		jamezzz	Fountain Parks (IOI21_parks)	C++17	25 / 100	805 ms	70288 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define maxn 200005
#define pb push_back

typedef pair<int,int> ii;

int dx[2]={2,0},dy[2]={0,2};
bool vis[maxn],bad[maxn],weird[maxn];
vector<ii> squares;
map<ii,int> fid,sid,eid,use;
vector<int> AL[maxn],par[maxn];
int p[maxn],rnk[maxn];

int fp(int i){return (p[i]==i)?i:p[i]=fp(p[i]);}
void join(int x,int y){
	x=fp(x),y=fp(y);
	if(x==y)return;
	if(rnk[x]<rnk[y])p[x]=y;
	else p[y]=x;
	if(rnk[x]==rnk[y])++rnk[x];
}

inline bool fin(int x,int y){
	return fid.find(ii(x,y))!=fid.end();
}

inline bool sin(int x,int y){
	return sid.find(ii(x,y))!=sid.end();
}

inline bool ein(int x,int y){
	return eid.find(ii(x,y))!=eid.end();
}

void dfs(int u,int p){
	//printf("dfs: %d %d\n",u,p);
	if(p!=-1){
		auto[x,y]=squares[u];
		ii f1,f2;
		if(p==par[u][0]){
			if((x+y)%4==0){//vertical
				f1={x-1,y-1},f2={x-1,y+1};
			}
			else{//horizontal
				f1={x-1,y-1},f2={x+1,y-1};
			}
		}
		else{
			if((x+y)%4==0){//vertical
				f1={x+1,y-1},f2={x+1,y+1};
			}
			else{//horizontal
				f1={x-1,y+1},f2={x+1,y+1};
			}
		}
		int i1=fid[f1],i2=fid[f2];
		if(ein(i1,i2))bad[eid[{i1,i2}]]=true;
		else bad[eid[{i2,i1}]]=true;
	}
	for(int v:AL[u]){
		if(vis[v])continue;
		vis[v]=true;
		dfs(v,u);
	}
}

int construct_roads(vector<int> x,vector<int> y){
    int n=x.size();
    for(int i=0;i<n;++i){
		fid[{x[i],y[i]}]=i;
	}
	int scnt=0,ecnt=0;
	for(int i=0;i<n;++i){
		if(fin(x[i]+2,y[i])&&fin(x[i],y[i]+2)&&fin(x[i]+2,y[i]+2)){
			sid[{x[i]+1,y[i]+1}]=scnt++;
			squares.push_back({x[i]+1,y[i]+1});
		}
		for(int j=0;j<2;++j){
			int nx=x[i]+dx[j],ny=y[i]+dy[j];
			if(fin(nx,ny))eid[{i,fid[{nx,ny}]}]=ecnt++;
		}
	}
	for(auto it=sid.begin();it!=sid.end();++it){
		auto[x,y]=it->fi;
		assert(it->se!=scnt);
		if((x+y)%4==0){//vertical
			for(int dx:{-2,2}){
				if(sin(x+dx,y)){
					AL[sid[{x+dx,y}]].push_back(it->se);
					par[it->se].push_back(sid[{x+dx,y}]);
				}
				else{
					AL[scnt].push_back(it->se);
					par[it->se].push_back(scnt);
				}
			}
		}
		else{//horizontal
			for(int dy:{-2,2}){
				if(sin(x,y+dy)){
					AL[sid[{x,y+dy}]].push_back(it->se);
					par[it->se].push_back(sid[{x,y+dy}]);
				}
				else{
					AL[scnt].push_back(it->se);
					par[it->se].push_back(scnt);
				}
			}
		}
	}
	vis[scnt]=true;
	dfs(scnt,-1);
	/*
	for(auto it=sid.begin();it!=sid.end();++it){
		auto[x,y]=it->fi;
		if((x+y)%4==0){//vertical
			int cnt=0;
			for(int dx:{-1,1}){
				ii f1={x+dx,y-1},f2={x+dx,y+1};
				int i1=fid[f1],i2=fid[f2];
				if(ein(i1,i2)&&!bad[eid[{i1,i2}]])++cnt;
				else if(ein(i2,i1)&&!bad[eid[{i2,i1}]])++cnt;
			}
			if(cnt==2)assert(false);
		}
		else{//horizontal
			int cnt=0;
			for(int dy:{-1,1}){
				ii f1={x-1,y+dy},f2={x+1,y+dy};
				int i1=fid[f1],i2=fid[f2];
				if(ein(i1,i2)&&!bad[eid[{i1,i2}]])++cnt;
				else if(ein(i2,i1)&&!bad[eid[{i2,i1}]])++cnt;
			}
			if(cnt==2)assert(false);
		}
	}
	*/
	for(int i=0;i<n;++i)p[i]=i;
	vector<int> u,v,a,b;
	for(auto it=eid.begin();it!=eid.end();++it){
		if(bad[it->se])continue;
		auto[i,j]=it->fi;
		if(fp(i)==fp(j))continue;
		join(i,j);
		int x1=x[i],x2=x[j],y1=y[i],y2=y[j];
		int bx,by;
		if(x1==x2){
			if((x1-1+(y1+y2)/2)%4==0)bx=x1-1,by=(y1+y2)/2;
			else bx=x1+1,by=(y1+y2)/2;
		}
		else{
			if(((x1+x2)/2+y1-1)%4!=0)bx=(x1+x2)/2,by=y1-1;
			else bx=(x1+x2)/2,by=y1+1;
		}
		u.pb(i),v.pb(j),a.pb(bx),b.pb(by);
		int idk=use[{bx,by}];
		use[{bx,by}]=true;
	}
	for(int i=0;i<n;++i){
		if(fp(i)!=fp(0))return 0;
	}
	build(u,v,a,b);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:161:7: warning: unused variable 'idk' [-Wunused-variable]
  161 |   int idk=use[{bx,by}];
      |       ^~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30