Submission #436668

#	Time	Username	Problem	Language	Result	Execution time	Memory
436668		dqhungdl	Fountain Parks (IOI21_parks)	C++17	70 / 100	925 ms	81128 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,bool> mark;
	vector<ii> benchesPos;
	map<ii,vector<int>> g;
	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;
			benchesPos.push_back({bx-1,by});
			benchesPos.push_back({bx+1,by});
			g[ii(bx-1,by)].push_back(i);
			g[ii(bx+1,by)].push_back(i);
		} else {
			int bx=x[path.first]+1,by=y[path.first];
			benchesPos.push_back({bx,by-1});
			benchesPos.push_back({bx,by+1});
			g[ii(bx,by-1)].push_back(i);
			g[ii(bx,by+1)].push_back(i);
		}
	}
	vector<ii> benches;
	if(*max_element(x.begin(),x.end())<=6) {
		for(int i=0;i<paths.size();i++) {
			if(!mark[benchesPos[2*i]]) {
				mark[benchesPos[2*i]]=true;
				benches.push_back(benchesPos[2*i]);
			} else {
				mark[benchesPos[2*i+1]]=true;
				benches.push_back(benchesPos[2*i+1]);
			}
		}
	} else {
		benches.resize(paths.size(),{-1,-1});
		for(int i=0;i<paths.size();i++)
			if(benches[i]==ii(-1,-1)) {
				int curId=i;
				ii curBenchPos=benchesPos[2*i];
				benches[curId]=curBenchPos;
				vector<int> gg=g[curBenchPos];
				while(gg.size()==2) {
					int u=gg[0],v=gg[1];
					if(u!=curId)
						swap(u,v);
					curId=v;
					if(benches[curId]!=ii(-1,-1))
						break;
					curBenchPos=(curBenchPos!=benchesPos[2*v]?benchesPos[2*v]:benchesPos[2*v+1]);
					benches[curId]=curBenchPos;
					gg=g[curBenchPos];
				}
			}
		for(ii bench:benches) {
			assert(!mark[bench]);
			mark[bench]=true;
		}
	}
	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:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i=0;i<paths.size();i++) {
      |               ~^~~~~~~~~~~~~
parks.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i=0;i<paths.size();i++)
      |               ~^~~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:126: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]
  126 |  if(paths.size()!=n-1)
      |     ~~~~~~~~~~~~^~~~~

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