Submission #1216720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216720		thelegendary08	Fountain Parks (IOI21_parks)	C++17	100 / 100	750 ms	45572 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>
#define vpii vector<pair<int,int>>
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl;
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();
	
	map<pii,int>m;
	ccs = n;
	f0r(i,n){
		m[mp(x[i], y[i])] = i;
		par[i] = i;
		sz[i] = 1;
	}
	
	vpii edges;
	f0r(i,n){
		for(auto u : adj(mp(x[i], y[i]))){
			if(m.count(u) && m[u] > i){
				edges.pb(mp(-(y[i] + u.second)/2, (x[i] + u.first)/2));
			}
		}
	}
	
	sort(edges.begin(), edges.end());
	
	set<pii>benches;
	f0r(i, edges.size()){
		int x = edges[i].second; int y = -edges[i].first;
		// cout<<x<<' '<<y<<'\n';
		if(x % 2 == 0){
			int u1 = m[mp(x, y-1)]; int u2 = m[mp(x, y+1)];
			if((x + y) % 4 == 1){
				// dout2(x-1,y);
				if(!benches.count(mp(x-1, y))){
					benches.insert(mp(x-1, y));
					u.pb(u1); v.pb(u2);
					a.pb(x-1); b.pb(y);
				}
			}
			else{
				// dout2(x+1,y);
				if(!benches.count(mp(x+1, y))){
					benches.insert(mp(x+1, y));
					u.pb(u1); v.pb(u2);
					a.pb(x+1); b.pb(y);
				}
			}
		}
		else{
			int u1 = m[mp(x-1, y)]; int u2 = m[mp(x+1, y)];
			if((x + y) % 4 == 3){
				// dout2(x,y+1);
				if(!benches.count(mp(x, y-1))){
					benches.insert(mp(x,y-1));
					u.pb(u1); v.pb(u2);
					a.pb(x); b.pb(y-1);
				}
				
			}
			else{
				// dout2(x,y-1);
				if(!benches.count(mp(x, y+1))){
					benches.insert(mp(x, y+1));
					u.pb(u1); v.pb(u2);
					a.pb(x); b.pb(y+1);
				}
			}
		}
	}
	f0r(i, u.size()){
		// dout2(u[i], v[i]);
		unite(u[i], v[i]);
	}
	if(ccs != 1)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: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30