Submission #436980

#	Time	Username	Problem	Language	Result	Execution time	Memory
436980		haojiandan	Fountain Parks (IOI21_parks)	C++17	100 / 100	951 ms	29040 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
const int maxn=(2e5)+10;
map<pair<int,int>,int> M;
int n,m,hd,tl;
bool vis[maxn];
int fx[4][2]={{-2,0},{2,0},{0,-2},{0,2}};
int q[maxn];
int construct_roads(vector<int> X,vector<int> Y) {
	n=(int)X.size();
	vector<int> u,v,a,b;
	
	for (int i=0;i<n;i++) M[MP(X[i],Y[i])]=i;
	hd=tl=1; q[1]=0; vis[0]=1;
	while (hd<=tl) {
		int x=X[q[hd]],y=Y[q[hd]]; hd++;
		for (int i=0;i<4;i++) {
			int xx=x+fx[i][0],yy=y+fx[i][1];
			if (M.count(MP(xx,yy))) {
				int id=M[MP(xx,yy)]; if (vis[id]) continue;
				vis[id]=1; q[++tl]=id;
			}
		}
	}
	if (tl!=n) return 0;
	
	for (int i=0;i<n;i++) {
		int x=X[i],y=Y[i];
		int A=x+2,B=y,flag;
		if (M.count(MP(A,B))) {
			flag=1;
			if ((x+y)&2) {
				if (M.count(MP(x,y+2))&&M.count(MP(x+2,y+2))) flag=0;
			}
			if (flag) {
				u.push_back(i),v.push_back(M[MP(A,B)]);
				a.push_back(x+1); if ((x+y)&2) b.push_back(y+1); else b.push_back(y-1);
			}
		}
		A=x,B=y+2;
		if (M.count(MP(A,B))) {
			flag=1;
			if (!((x+y)&2)) {
				if (M.count(MP(x+2,y))&&M.count(MP(x+2,y+2))) flag=0;
			}
			if (flag) {
				u.push_back(i),v.push_back(M[MP(A,B)]);
				if ((x+y)&2) a.push_back(x-1); else a.push_back(x+1); b.push_back(y+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