Submission #436578

#	Time	Username	Problem	Language	Result	Execution time	Memory
436578		dqhungdl	Fountain Parks (IOI21_parks)	C++17	5 / 100	793 ms	61408 KiB

parks

#include "parks.h"

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

typedef pair<int,int> ii;
int n;
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 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});
	}
	if(paths.size()<n-1)
		return 0;
	sort(paths.begin(),paths.end(),cmp);
	//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:28: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]
   28 |  for(int i=0;i<paths.size();i++) {
      |              ~^~~~~~~~~~~~~
parks.cpp:45: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]
   45 |  for(int i=0;i<paths.size();i++) {
      |              ~^~~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:73: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]
   73 |  if(paths.size()<n-1)
      |     ~~~~~~~~~~~~^~~~

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