Submission #1215952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215952		thelegendary08	Fountain Parks (IOI21_parks)	C++17	30 / 100	602 ms	101604 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define mp make_pair
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define pii pair<int,int>
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<endl;
#define vvi vector<vi>
#define vb vector<bool>
using namespace std;
vector<pii> adj(pii x){
	int a = x.first; int b = x.second;
	return {mp(a+2, b), mp(a-2, b), mp(a, b+2), mp(a, b-2)};
}

const int mxn = 2e5 + 5;
vi sz(mxn), par(mxn);
int find(int x){
	while(x != par[x])x = par[x];
	return x;
}
int ccs;
void unite(int a, int b){
	a = find(a); b = find(b); 
	if(a == b)return;
	ccs--;
	if(sz[a] < sz[b])swap(a,b);
	sz[a] += sz[b];
	par[b] = a;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
	// vector<vector<int>>grid(2, vi(mxn, -1));
	vi u,v,a,b;
	int n = x.size();
	vector<vector<int>>grid(3, vi(mxn, -1));
	f0r(i,n){
		int a = x[i] / 2 - 1;
		int b = y[i] / 2 - 1;
		grid[a][b] = i;
	}
	int fi = -1;
	f0r(i, mxn){
		if(grid[0][i] != -1 || grid[1][i] != -1 || grid[2][i] != -1){
			fi = i; break;
		}
	}
	
	int done = 0;
	if(grid[0][fi] != -1 && grid[1][fi] != -1){
		u.pb(grid[0][fi]); v.pb(grid[1][fi]);
	}
	if(grid[1][fi] != -1 && grid[2][fi] != -1){
		u.pb(grid[1][fi]); v.pb(grid[2][fi]);
	}
	done += (grid[0][fi] != -1) + (grid[1][fi] != -1) + (grid[2][fi] != -1);
	bool ok = 1;
	FOR(i, fi + 1, mxn){
		if(done == n)break;
		if(grid[0][i] == -1 && grid[1][i] == -1 && grid[2][i] == -1){
			ok = 0;
			break;
		}
		vb vis(3);
		f0r(j,3){
			if(grid[j][i] == -1)vis[j] = 1;
		}
		if(grid[0][i] != -1 && grid[0][i-1] != -1){
			u.pb(grid[0][i]);v.pb(grid[0][i-1]); vis[0] = 1;
		}
		if(grid[1][i] != -1 && grid[1][i-1] != -1){
			u.pb(grid[1][i]); v.pb(grid[1][i-1]); vis[1] = 1;
		}
		if(grid[2][i] != -1 && grid[2][i-1] != -1){
			u.pb(grid[2][i]); v.pb(grid[2][i-1]); vis[2] = 1;
		}
		if(!vis[1]){
			if(vis[0] && grid[0][i] != -1){
				u.pb(grid[0][i]); v.pb(grid[1][i]); vis[1] = 1;
			}
			if(vis[2] && grid[2][i] != -1){
				u.pb(grid[2][i]); v.pb(grid[1][i]); vis[1] = 1;
			}
		}
		
		if(!vis[0]){
			if(!vis[1] || grid[1][i] == -1){
				
			}
			else{
				u.pb(grid[0][i]); v.pb(grid[1][i]); vis[0] = 1;
			}
		}
		if(!vis[2]){
			if(!vis[1] || grid[1][i] == -1){
				
			}
			else{
				u.pb(grid[1][i]); v.pb(grid[2][i]); vis[2] = 1;
			}
		}
		done += (grid[0][i] != -1) + (grid[1][i] != -1) + (grid[2][i] != -1);
	}
	// vout(u);
	// vout(v);
	if(!ok)return 0;
	
	
	
	map<pii,int>m;
	ccs = n;
	f0r(i,n){
		m[mp(x[i], y[i])] = i;
		par[i] = i;
		sz[i] = 1;
	}
	
	map<pii,vi>fight;
	map<pii,int>fc;
	/*
	f0r(i,n){
		for(auto s : adj(mp(x[i], y[i]))){
			if(m.count(s) && m[s] > i){
				if(find(i) != find(m[s])){
					u.pb(i); v.pb(m[s]);
					unite(i, m[s]);
					int x1 = x[i]; int y1 = y[i]; int x2 = x[m[s]]; int y2 = y[m[s]];
					if(x1 == x2){
						fight[mp(x1 + 1, (y1 + y2) / 2)].pb(u.size() - 1);
						fight[mp(x1 - 1, (y1 + y2) / 2)].pb(u.size() - 1);
					}
					else{
						fight[mp((x1 + x2) / 2, y1 + 1)].pb(u.size() - 1);
						fight[mp((x1 + x2) / 2, y1 - 1)].pb(u.size() - 1);
					}
				}
				
			}
		}
	}
	*/
	f0r(i, u.size()){
		int x1 = x[u[i]]; int y1 = y[u[i]]; int x2 = x[v[i]]; int y2 = y[v[i]];
		unite(u[i], v[i]);
		if(x1 == x2){
			fight[mp(x1 + 1, (y1 + y2) / 2)].pb(i);
			fight[mp(x1 - 1, (y1 + y2) / 2)].pb(i);
		}
		else{
			fight[mp((x1 + x2) / 2, y1 + 1)].pb(i);
			fight[mp((x1 + x2) / 2, y1 - 1)].pb(i);
		}
	}
	
	if(ccs > 1)return 0;
	
	int visd = 0;
	queue<pii>q; //stores benches
	vb vis(u.size());
	a.resize(u.size()); b.resize(u.size());
	set<pii>twos;
	for(auto u : fight){
		// vout(u.second);
		fc[u.first] = u.second.size();
		if(fc[u.first] == 1){
			q.push(u.first);
		}
		if(fc[u.first] == 2){
			twos.insert(u.first);
		}
	}
	
	int iter = 0;
	while(visd < u.size()){
		if(q.empty()){
			q.push(*twos.begin());
		}
		
		
		while(!q.empty()){
			pii node = q.front(); q.pop();
			fc[node] = 0; twos.erase(node);
			// cout<<node.first<<' '<<node.second<<'\n';
			for(auto cur : fight[node]){
				if(!vis[cur]){
					a[cur] = node.first; b[cur] = node.second; vis[cur] = 1; visd++;
					int x1 = x[u[cur]]; int x2 = x[v[cur]]; int y1 = y[u[cur]]; int y2 = y[v[cur]];
					if(x1 == x2){
						if(fc.count(mp(x1 + 1, (y1 + y2) / 2))){
							int thing = --fc[mp(x1 + 1, (y1 + y2) / 2)];
							if(thing == 1){
								q.push(mp(x1 + 1, (y1 + y2) / 2));
								twos.erase(mp(x1 + 1, (y1 + y2) / 2));
							}
							else if(thing == 2){
								twos.insert(mp(x1 + 1, (y1 + y2) / 2));
							}
						}
						if(fc.count(mp(x1 - 1, (y1 + y2) / 2))){
							int thing = --fc[mp(x1 - 1, (y1 + y2) / 2)];
							if(thing == 1){
								q.push(mp(x1 - 1, (y1 + y2) / 2));
								twos.erase(mp(x1 - 1, (y1 + y2) / 2));
							}
							else if(thing == 2){
								twos.insert(mp(x1 - 1, (y1 + y2) / 2));
							}
						}
					}
					else{
						if(fc.count(mp((x1 + x2) / 2, y1 + 1))){
							int thing = --fc[mp((x1 + x2) / 2, y1 + 1)];
							if(thing == 1){
								q.push(mp((x1 + x2) / 2, y1 + 1));
								twos.erase(mp((x1 + x2) / 2, y1 + 1));
							}
							else if(thing == 2){
								twos.insert(mp((x1 + x2) / 2, y1 + 1));
							}
						}
						if(fc.count(mp((x1 + x2) / 2, y1 - 1))){
							int thing = --fc[mp((x1 + x2) / 2, y1 - 1)];
							if(thing == 1){
								q.push(mp((x1 + x2) / 2, y1 - 1));
								twos.erase(mp((x1 + x2) / 2, y1 - 1));
							}
							else if(thing == 2){
								twos.insert(mp((x1 + x2) / 2, y1 - 1));
							}
						}
					}
					break;
				}
			}
			
		}
	}
	
	
	/*
	bool ok = 1;
	f0r(i, u.size()){
		if(!vis[i])ok= 0;
	}
	if(!ok)return 0;
	*/
	build(u,v,a,b);
	return 1;
	
	
	
	/*
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    std::vector<int> u, v, a, b;
    u.push_back(0);
    v.push_back(1);
    a.push_back(x[0]+1);
    b.push_back(y[0]-1);
    build(u, v, a, b);
    return 1;
    */
}

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