Submission #1044720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044720		s_tree	Fountain Parks (IOI21_parks)	C++17	45 / 100	726 ms	38144 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct dsu {
	vector<int> e;
	int cc=0;
	dsu(int n) {
		cc=n;
		e=vector<int>(n+1, -1);
	}
	int get(int x) {return e[x]<0?x:e[x]=get(e[x]);}
	bool unite(int a, int b) {
		a=get(a),b=get(b);
		if(a==b)return false;
		if(-e[a] > -e[b]) {
			swap(a, b);
		}
		e[b]+=e[a];
		e[a]=b;
		cc--;
//		cout << a << " " << b << endl;
		return true;
	}
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
	int n = x.size();
	map<pair<int,int>, int> mp;
	vector<pair<int,int>> ben;
	for(int i = 0;i<n;i++) {
		mp[{x[i], y[i]}] = i;
	}
	vector<pair<int,int>> blB, whB;
	dsu d(n);
	for(int i = 0;i<n;i++) {
		ben.pb({x[i]+1, y[i]+1});
		ben.pb({x[i]-1, y[i]+1});
		ben.pb({x[i]+1, y[i]-1});
		ben.pb({x[i]-1, y[i]-1});
		if(mp.find(pair{x[i]+2, y[i]})!=mp.end()) {
			d.unite(mp[{x[i]+2, y[i]}], i);
		}
		if(mp.find(pair{x[i], y[i]+2})!=mp.end()) {
			d.unite(mp[{x[i], y[i]+2}], i);
		}
	}
	if(d.cc!=1)return 0;
	dsu d2(n+1);
	vector<int> a, b, c,D ;
	for(auto [xx, yy]:ben) {
		if((xx+yy)%4 == 0) {
			pair<int,int> A = {xx+1, yy+1};
			pair<int,int> B = {xx+1, yy-1};
			if(mp.find(A)!=mp.end() and mp.find(B)!=mp.end() and d2.unite(mp[A], mp[B])) {
				a.push_back(mp[A]);
				b.push_back(mp[B]);
				c.push_back(xx);
				D.push_back(yy);
				continue;
			}
			A.first-=2, B.first-=2;
			if(mp.find(A)!=mp.end() and mp.find(B)!=mp.end() and d2.unite(mp[A], mp[B])) {
				a.push_back(mp[A]);
				b.push_back(mp[B]);
				c.push_back(xx);
				D.push_back(yy);
				continue;
			}
		}
		else {
			pair<int,int> A = {xx+1, yy+1};
			pair<int,int> B = {xx-1, yy+1};
			if(mp.find(A)!=mp.end() and mp.find(B)!=mp.end() and d2.unite(mp[A], mp[B])) {
				a.push_back(mp[A]);
				b.push_back(mp[B]);
				c.push_back(xx);
				D.push_back(yy);
				continue;
			}
			A.second-=2, B.second-=2;
			if(mp.find(A)!=mp.end() and mp.find(B)!=mp.end() and d2.unite(mp[A], mp[B])) {
				a.push_back(mp[A]);
				b.push_back(mp[B]);
				c.push_back(xx);
				D.push_back(yy);
				continue;
			}
		}
	}
	build(a, b, c, D);
	return 1;
}

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