Submission #436584

#	Time	Username	Problem	Language	Result	Execution time	Memory
436584		dqhungdl	Fountain Parks (IOI21_parks)	C++17	15 / 100	815 ms	62164 KiB

parks

#include "parks.h"

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
const int MAX=2e5+5;
int n,P[MAX];
vector<int> x,y;
map<ii,int> M;

bool isVertical(ii u) {
	return x[u.first]==x[u.second];
}

bool cmp(ii u,ii v) {
	if(x[u.first]==x[v.first]) {
		if(isVertical(u)==isVertical(v))
			return y[u.first]<y[v.first];
		return isVertical(u)>isVertical(v);
	}
	return x[u.first]<x[v.first];
}

vector<ii> constructBenches(vector<ii> &paths) {
	map<ii,int> deg;
	map<ii,bool> mark;
	vector<ii> benchesPos;
	for(int i=0;i<paths.size();i++) {
		ii path=paths[i];
		if(x[path.first]==x[path.second]) {
			int bx=x[path.first],by=y[path.first]+1;
			deg[ii(bx-1,by)]++;
			deg[ii(bx+1,by)]++;
			benchesPos.push_back({bx-1,by});
			benchesPos.push_back({bx+1,by});
		} else {
			int bx=x[path.first]+1,by=y[path.first];
			deg[ii(bx,by-1)]++;
			deg[ii(bx,by+1)]++;
			benchesPos.push_back({bx,by-1});
			benchesPos.push_back({bx,by+1});
		}
	}
	vector<ii> benches;
	for(int i=0;i<paths.size();i++) {
		if(deg[benchesPos[2*i+1]]==1||mark[benchesPos[2*i]]) {
			mark[benchesPos[2*i+1]]=true;
			deg[benchesPos[2*i+1]]--;
			benches.push_back(benchesPos[2*i+1]);
		} else {
			mark[benchesPos[2*i]]=true;
			deg[benchesPos[2*i]]--;
			benches.push_back(benchesPos[2*i]);
		}
	}
	return benches;
}

int find(int u) {
	if(u==P[u])
		return u;
	return P[u]=find(P[u]);
}

void merge(int u,int v) {
	if(u>v)
		swap(u,v);
	P[u]=v;
}

vector<ii> removePaths(vector<ii> paths) {
	for(int i=0;i<n;i++)
		P[i]=i;
	vector<ii> newPaths;
	for(ii path:paths) {
		int u=find(path.first),v=find(path.second);
		if(u!=v) {
			merge(u,v);
			newPaths.push_back(path);
		}
	}
	return newPaths;
}

int construct_roads(std::vector<int> _x, std::vector<int> _y) {
	n=_x.size();
	x=_x,y=_y;
	for(int i=0;i<n;i++)
		M[ii(x[i],y[i])]=i;
	vector<ii> paths;
	for(int i=0;i<n;i++) {
		auto it=M.find({x[i]+2,y[i]});
		if(it!=M.end())
			paths.push_back({i,it->second});
		it=M.find({x[i],y[i]+2});
		if(it!=M.end())
			paths.push_back({i,it->second});
	}
	sort(paths.begin(),paths.end(),cmp);
	paths = removePaths(paths);
	if(paths.size()!=n-1)
		return 0;
	//for(ii path:paths)
	//	cerr<<x[path.first]<<' '<<y[path.first]<<' '<<x[path.second]<<' '<<y[path.second]<<'\n';
	vector<ii> benches=constructBenches(paths);
	vector<int> U(n-1),V(n-1),A(n-1),B(n-1);
	for(int i=0;i<n-1;i++) {
		U[i]=paths[i].first,V[i]=paths[i].second;
		A[i]=benches[i].first,B[i]=benches[i].second;
	}
	build(U,V,A,B);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'std::vector<std::pair<int, int> > constructBenches(std::vector<std::pair<int, int> >&)':
parks.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i=0;i<paths.size();i++) {
      |              ~^~~~~~~~~~~~~
parks.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i=0;i<paths.size();i++) {
      |              ~^~~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:102:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |  if(paths.size()!=n-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