Submission #1040841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040841		Dan4Life	Fountain Parks (IOI21_parks)	C++17	70 / 100	313 ms	121612 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
using ll = long long;
using ar2 = array<int,2>;
using ar3 = array<int,3>;

const int mxN = (int)2e5+10;
int n;
struct Edge{
	int fa, fb, x, y;
	Edge(int a=0, int b=0, int _x=-1, int _y=-1){
		fa=a, fb=b, x=_x, y=_y;
	}
};
vector<Edge> edges;
vector<ar3> fountains, origFountains;
vector<int> adj[mxN];
set<ar2> usedB;

template<int SZ> struct DSU{
	int p[SZ];
	vector<int> comp[SZ];
	void init(int n){
		for(int i = 0; i < n; i++){
			p[i]=i; comp[i].clear();
			comp[i].pb(i);
		}
	}
	
	int findSet(int i){return p[i]==i?i:p[i]=findSet(p[i]);}
	bool isSameSet(int i, int j) {return findSet(i)==findSet(j);}
	void unionSet(int i, int j){
		int x = findSet(i), y = findSet(j);
		if(x==y) return;
		adj[i].pb(j); adj[j].pb(i);
		if(sz(comp[x]) < sz(comp[y])) swap(x,y);
		p[y]=x; for(auto u : comp[y]) comp[x].pb(u);
	}
	int findSz(int i) { return sz(comp[findSet(i)]); }
};
DSU<mxN> dsu;

set<int> horEdge[mxN], verEdge[mxN];

void dfs(int s, int p, bool turn){
	if(p!=-1){
		if(origFountains[s][0]==origFountains[p][0]){
			int x = origFountains[s][0], y = min(origFountains[s][1],origFountains[p][1])+1;
			int x1 = x-1, x2 = x+1;
			if(!turn) verEdge[x].insert(y-1);
			else{
				bool ok = 0;
				if(horEdge[y-1].count(x-2) and usedB.count({x1,y-2})) ok=1;
				if(horEdge[y+1].count(x-2) and usedB.count({x1,y+2})) ok=1;
				if(ok) swap(x1,x2);
				
				if(usedB.count({x1,y})) swap(x1,x2);
				if(usedB.count({x1,y})){ dsu.init(n); return; }
				edges.pb(Edge(s,p,x1,y)); usedB.insert({x1,y});
				verEdge[x].erase(y-1);
			}
		}
		else{
			int x = min(origFountains[s][0],origFountains[p][0])+1, y = origFountains[s][1];
			int y1 = y-1, y2 = y+1;
			if(!turn) horEdge[y].insert(x-1);
			else{
				bool ok = 0;
				if(verEdge[x-1].count(y-2) and usedB.count({x-2,y1})) ok=1;
				if(verEdge[x+1].count(y-2) and usedB.count({x+2,y1})) ok=1;
				if(ok) swap(y1,y2);
				
				if(usedB.count({x,y1})) swap(y1,y2);
				if(usedB.count({x,y1})){ dsu.init(n); return; }
				edges.pb(Edge(s,p,x,y1)); usedB.insert({x,y1});
				horEdge[y].erase(x-1);
			}
		}
	}
	for(auto u : adj[s]){
		if(u==p) continue;
		dfs(u,s,turn);
	}
}

int construct_roads(vi x, vi y) {
	n = sz(x); dsu.init(n);
	if (n==1){ build({}, {}, {}, {}); return 1; }
	int mnX = *min_element(all(x));
	int mxX = *max_element(all(x));
	for(int i = 0; i < n; i++){
		fountains.pb({x[i],y[i],i});
		origFountains.pb({x[i],y[i],i});
	}
	
	if(mnX==mxX){
		sort(all(fountains),[&](ar3 a, ar3 b){ return a[1]<b[1]; });
		for(int i = 1; i < sz(fountains); i++){
			if(fountains[i][1]-fountains[i-1][1]==2){
				auto [x1,y1,a] = fountains[i-1];
				auto [x2,y2,b] = fountains[i];
				dsu.unionSet(a,b);
				edges.pb(Edge(a,b,x1-1,y1+1));
			}
		}
	}
	else if(mxX-mnX==2){
		sort(all(fountains),[&](ar3 a, ar3 b){ 
			if(a[0]!=b[0]) return a[0]<b[0];
			return a[1]<b[1]; 
		});
		set<ar2> S; S.clear();
		for(int i = sz(fountains)-1; i>=0; i--){
			if(fountains[i][0]!=mxX) break;
			S.insert({fountains[i][1], fountains[i][2]});
		}
		for(int i = 1; i < sz(fountains); i++){
			if(fountains[i][0]!=fountains[i-1][0]) continue;
			if(fountains[i][1]-fountains[i-1][1]==2){
				auto [x1,y1,a] = fountains[i-1];
				auto [x2,y2,b] = fountains[i];
				dsu.unionSet(a,b);
				if(x1==mnX) edges.pb(Edge(a,b,x1-1,y1+1));
				else edges.pb(Edge(a,b,x1+1,y1+1));
			}
		}
		
		for(int i = 0; i < sz(fountains); i++){
			auto [x1,y1,a] = fountains[i];
			if(x1!=mnX) break;
			auto itr = S.lower_bound({y1,-1});
			if(itr==end(S) or (*itr)[0]!=y1) continue;
			int b = (*itr)[1];
			dsu.unionSet(a,b);
			edges.pb(Edge(a,b,x1+1,y1-1));
		}
	}
	else if(mxX-mnX==4){
		sort(all(fountains),[&](ar3 a, ar3 b){ 
			if(a[0]!=b[0]) return a[0]<b[0];
			return a[1]<b[1]; 
		});
		set<ar2> S[mxN];
		for(int i = sz(fountains)-1; i>=0; i--)
			S[fountains[i][0]].insert({fountains[i][1], fountains[i][2]});
		for(int i = 1; i < sz(fountains); i++){
			if(fountains[i][0]!=fountains[i-1][0]) continue;
			if(fountains[i][1]-fountains[i-1][1]==2){
				auto [x1,y1,a] = fountains[i-1];
				auto [x2,y2,b] = fountains[i];
				dsu.unionSet(a,b);
				if(x1==mnX) edges.pb(Edge(a,b,x1-1,y1+1)), usedB.insert({x1-1,y1+1});
				else if(x1==mxX) edges.pb(Edge(a,b,x1+1,y1+1)), usedB.insert({x1+1,y1+1});
				else edges.pb(Edge(a,b,y1%4==0?x1-1:x1+1,y1+1)), usedB.insert({y1%4==0?x1-1:x1+1,y1+1});
			}
		}
		for(int i = 0; i < sz(fountains); i++){
			auto [x1,y1,a] = fountains[i];
			auto itr = S[x1+2].lower_bound({y1,-1});
			if(itr==end(S[x1+2]) or (*itr)[0]!=y1) continue;
			int b = (*itr)[1];
			
			if(!usedB.count({x1+1,y1-1})){
				dsu.unionSet(a,b);
				edges.pb(Edge(a,b,x1+1,y1-1));
				usedB.insert({x1+1,y1-1});
			}
			else if(!usedB.count({x1+1,y1+1})){
				dsu.unionSet(a,b);
				edges.pb(Edge(a,b,x1+1,y1+1));
				usedB.insert({x1+1,y1+1});
			}			
		}
	}
	else{
		sort(all(fountains),[&](ar3 a, ar3 b){ 
			if(a[0]!=b[0]) return a[0]<b[0];
			return a[1]<b[1]; 
		});
		set<ar2> S[mxN];
		for(int i = sz(fountains)-1; i>=0; i--)
			S[fountains[i][0]].insert({fountains[i][1], fountains[i][2]});
		for(int i = 1; i < sz(fountains); i++){
			if(fountains[i][0]!=fountains[i-1][0]) continue;
			if(fountains[i][1]-fountains[i-1][1]==2){
				auto [x1,y1,a] = fountains[i-1];
				auto [x2,y2,b] = fountains[i];
				dsu.unionSet(a,b);
			}
		}
		for(int i = 0; i < sz(fountains); i++){
			auto [x1,y1,a] = fountains[i];
			auto itr = S[x1+2].lower_bound({y1,-1});
			if(itr==end(S[x1+2]) or (*itr)[0]!=y1) continue;
			int b = (*itr)[1];
			dsu.unionSet(a,b);
		}
		for(int i = 0; i < n; i++){
			if(sz(adj[i])!=1) continue;
			dfs(i,-1, 0); dfs(i,-1, 1); break;
		}
	}
	if(dsu.findSz(0)!=n) return 0;
    vi U, V, A, B;
    for(auto edge : edges){
		U.pb(edge.fa), V.pb(edge.fb);
		A.pb(edge.x), B.pb(edge.y);
	}
	build(U,V,A,B); return 1;
}

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