Submission #951205

#	Time	Username	Problem	Language	Result	Execution time	Memory
951205		Trisanu_Das	Fountain Parks (IOI21_parks)	C++17	45 / 100	470 ms	58920 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
vector<int>g[MAXN];
map<pair<int,int>,int> tochki;
bool vis[MAXN];
vector<pair<int,int> >roads;
int cnt;
void dfs(int u)
{
	vis[u]=1;
	cnt++;
	for(auto xd:g[u])
	{
		if(vis[xd])continue;
		dfs(xd);
		roads.push_back({u,xd});
	}
}
int construct_roads(vector<int> x, vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    for(int i=0;i<x.size();i++)
    {
		tochki[make_pair(x[i],y[i])]=i;
	}
	for(int i=0;i<x.size();i++)
	{
		if(tochki.count(make_pair(x[i],y[i]-2)))
		{
			g[i].push_back(tochki[make_pair(x[i],y[i]-2)]);
		}
		if(tochki.count(make_pair(x[i],y[i]+2)))
		{
			g[i].push_back(tochki[make_pair(x[i],y[i]+2)]);
		}
		if(tochki.count(make_pair(x[i]+2,y[i])))
		{
			g[i].push_back(tochki[make_pair(x[i]+2,y[i])]);
		}
		if(tochki.count(make_pair(x[i]-2,y[i])))
		{
			g[i].push_back(tochki[make_pair(x[i]-2,y[i])]);
		}
	}
	dfs(0);
	if(cnt!=x.size())return 0;
	vector<int>u;
	vector<int>v;
	vector<int>a;
	vector<int>b;
	for(int i=0;i<roads.size();i++)
	{
		u.push_back(roads[i].first);
		v.push_back(roads[i].second);
		if(x[roads[i].first]==x[roads[i].second])
		{
			int x1=x[roads[i].first];
			int y1=min(y[roads[i].first],y[roads[i].second]);
			if((x1+y1)%4==0)
			{
				a.push_back(x1+1);
				b.push_back(y1+1);
			}
			else
			{
				a.push_back(x1-1);
				b.push_back(y1+1);
			}
		}
		else
		{
			int y1=y[roads[i].first];
			int x1=min(x[roads[i].first],x[roads[i].second]);
			if((x1+y1)%4==0)
			{
				a.push_back(x1+1);
				b.push_back(y1-1);
			}
			else
			{
				a.push_back(x1+1);
				b.push_back(y1+1);
			}
		}
	}
	build(u,v,a,b);
	return 1;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~
parks.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i=0;i<x.size();i++)
      |              ~^~~~~~~~~
parks.cpp:50:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  if(cnt!=x.size())return 0;
      |     ~~~^~~~~~~~~~
parks.cpp:55: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]
   55 |  for(int i=0;i<roads.size();i++)
      |              ~^~~~~~~~~~~~~

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