Submission #1070557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070557		jamjanek	Fountain Parks (IOI21_parks)	C++17	100 / 100	423 ms	34432 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int>mapa;
int roza[4][2] = {{0,-2}, {0,2}, {-2,0}, {2,0}};
int father[200010];
int find(int x){
	if(father[x]==x)return x;
	return father[x] = find(father[x]);
}
int construct_roads(vector<int> x, vector<int> y) {
	vector<int>va,vb,vu,vv;
	int n = x.size(), i;
	vector<pair<int,int>>p;
	for(i=0;i<n;i++){
		mapa[{x[i],y[i]}]=i;
		p.push_back({x[i], y[i]});
	}
	sort(p.begin(), p.end());
	for(i=0;i<n;i++)father[i] = i;
	for(int j = 0;j<n;j++){
		i = mapa[p[j]];
		if(mapa.find({x[i],y[i]})!=mapa.end() && mapa.find({x[i]+2, y[i]})!=mapa.end() && mapa.find({x[i], y[i]+2})!=mapa.end() && mapa.find({x[i]+2, y[i]+2})!=mapa.end()){
//			printf("znalazlem\n");
			int a=mapa[{x[i],y[i]}];
			int b=mapa[{x[i]+2,y[i]}];
			int c=mapa[{x[i],y[i]+2}];
			int d=mapa[{x[i]+2,y[i]+2}];
			if((x[i]+y[i]+2)%4==2){
				if(find(a)!=find(c)){
					vu.push_back(a);
					vv.push_back(c);
					father[find(a)]=find(c);
					va.push_back(x[i]-1);
					vb.push_back(y[i]+1);
				}
				if(find(b)!=find(d)){
					vu.push_back(b);
					vv.push_back(d);
					father[find(b)]=find(d);
					va.push_back(x[i]+3);
					vb.push_back(y[i]+1);
				}
				if(find(a)!=find(b)){
					vu.push_back(a);
					vv.push_back(b);
					father[find(a)] = find(b);
					va.push_back(x[i]+1);
					vb.push_back(y[i]+1);
				}
			}
			else{
				if(find(a)!=find(b)){
					vu.push_back(a);
					vv.push_back(b);
					father[find(a)]=find(b);
					va.push_back(x[i]+1);
					vb.push_back(y[i]-1);
				}
				if(find(c)!=find(d)){
					vu.push_back(c);
					vv.push_back(d);
					father[find(c)]=find(d);
					va.push_back(x[i]+1);
					vb.push_back(y[i]+3);
				}
				if(find(a)!=find(c)){
					vu.push_back(a);
					vv.push_back(c);
					father[find(a)] = find(c);
					va.push_back(x[i]+1);
					vb.push_back(y[i]+1);
				}				
			}
		}
	}
	for(int ij=0;ij<n;ij++){
		i = mapa[p[ij]];
		for(auto j: roza){
			if(mapa.find({x[i]+j[0], y[i]+j[1]})!=mapa.end()){
				if(find(i)==find(mapa[{x[i]+j[0], y[i]+j[1]}]))continue;
				father[find(i)] = find(mapa[{x[i]+j[0], y[i]+j[1]}]);
				vu.push_back(mapa[{x[i]+j[0], y[i]+j[1]}]);
				vv.push_back(i);
				int A = x[i]+j[0]/2, B = y[i]+j[1]/2;
				//printf("%d %d\n", A, B);
				if(j[1]==0){
					if((A+B)%4==1)
						va.push_back(A),vb.push_back(B+1);
					else
						va.push_back(A),vb.push_back(B-1);
				}
				else{
					if((A+B)%4==1)
						va.push_back(A-1),vb.push_back(B);
					else
						va.push_back(A+1),vb.push_back(B);
				}
			}
		}
	}
	for(i=0;i<n;i++)
		if(find(i)!=find(0))return 0;
	build(vu,vv,va,vb);
	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