Submission #1215875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215875		thelegendary08	Fountain Parks (IOI21_parks)	C++17	15 / 100	1263 ms	99132 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<<'\n';
#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));
	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;
	}
	
	vi u,v,a,b;
	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){
				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);
				}
			}
		}
	}
	
	if(ccs > 1)return 0;
	
	queue<pii>q; //stores benches
	for(auto u : fight){
		fc[u.first] = u.second.size();
		if(u.second.size() == 1){
			q.push(u.first);
		}
	}
	
	vb vis(u.size());
	a.resize(u.size()); b.resize(u.size());
	while(!q.empty()){
		pii node = q.front(); q.pop();
		for(auto cur : fight[node]){
			if(!vis[cur]){
				a[cur] = node.first; b[cur] = node.second; vis[cur] = 1;
				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))){
						fc[mp(x1 + 1, (y1 + y2) / 2)]--;
						if(fc[mp(x1 + 1, (y1 + y2) / 2)] == 1){
							q.push(mp(x1 + 1, (y1 + y2) / 2));
						}
					}
					if(fc.count(mp(x1 - 1, (y1 + y2) / 2))){
						fc[mp(x1 - 1, (y1 + y2) / 2)]--;
						if(fc[mp(x1 - 1, (y1 + y2) / 2)] == 1){
							q.push(mp(x1 - 1, (y1 + y2) / 2));
						}
					}
				}
				else{
					if(fc.count(mp((x1 + x2) / 2, y1 + 1))){
						fc[mp((x1 + x2) / 2, y1 + 1)]--;
						if(fc[mp((x1 + x2) / 2, y1 + 1)] == 1){
							q.push(mp((x1 + x2) / 2, y1 + 1));
						}
					}
					if(fc.count(mp((x1 + x2) / 2, y1 - 1))){
						fc[mp((x1 + x2) / 2, y1 - 1)]--;
						if(fc[mp((x1 + x2) / 2, y1 - 1)] == 1){
							q.push(mp((x1 + x2) / 2, y1 - 1));
						}
					}
				}
			}
		}
		
	}
	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: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30