Submission #598074

#	Time	Username	Problem	Language	Result	Execution time	Memory
598074		yutabi	Split the Attractions (IOI19_split)	C++14	40 / 100	91 ms	16384 KiB

split

#include "split.h"


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


#define pb push_back


typedef pair <int,int> ii;


vector <int> ans(100005);
vector <int> fnl(100005);
vector <bool> v;

int edge=-1;
int node1=-1;
int node2=-1;


int N;

int A,B,C;

vector <vector <ii> > graph(100005);

int DFS(int node, int par=-1)
{
	v[node]=1;

	int sum=1;

	for(int i=0;i<graph[node].size();i++)
	{
		if(v[graph[node][i].first]==0 && graph[node][i].first!=par)
		{
			int res=DFS(graph[node][i].first,node);

			sum+=res;

			ans[graph[node][i].second]=res;

			if(res>=A && N-res>=B)
			{
				node1=graph[node][i].first;
				node2=node;
				edge=graph[node][i].second;
			}

			if(N-res>=A && res>=B)
			{
				node2=graph[node][i].first;
				node1=node;
				edge=graph[node][i].second;
			}
		}
	}

	return sum;
}

int k;

int u;

void DFS2(int node, int par, int cl)
{
	v[node]=1;

	fnl[node]=cl;
	k++;

	for(int i=0;k<u && i<graph[node].size();i++)
	{
		if(v[graph[node][i].first]==0 && graph[node][i].first!=par)
		{
			DFS2(graph[node][i].first,node,cl);
		}
	}
}


vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
	int m=p.size();

	for(int i=0;i<m;i++)
	{
		graph[p[i]].pb(ii(q[i],i));
		graph[q[i]].pb(ii(p[i],i));
	}

	if(a==1)
	{
		fnl=vector <int> (n,3);

		k=0;
		u=b;

		v=vector <bool> (n,0);

		DFS2(0,-1,2);

		for(int i=0;i<n;i++)
		{
			if(fnl[i]==3)
			{
				fnl[i]=1;

				break;
			}
		}

		return fnl;
	}

	int small=a;
	int mid=b;
	int large=c;

	int remap[]={1,2,3};

	if(a>b)
	{
		swap(a,b);

		swap(remap[0],remap[1]);
	}
	
	if(b>c)
	{
		swap(c,b);

		swap(remap[2],remap[1]);
	}
	
	if(a>b)
	{
		swap(a,b);

		swap(remap[0],remap[1]);
	}

	N=n;
	A=a;
	B=b;
	C=c;

	v=vector <bool> (n,0);

	DFS(0);

	if(node1==-1)
	{
		return vector <int> (n,0);
	}

	fnl=vector <int> (n,remap[2]);

	k=0;
	u=A;

	v=vector <bool> (n,0);

	DFS2(node1,node2,remap[0]);


	k=0;
	u=B;

	DFS2(node2,node1,remap[1]);


	return fnl;
}

Compilation message (stderr)

split.cpp: In function 'int DFS(int, int)':
split.cpp:35: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]
   35 |  for(int i=0;i<graph[node].size();i++)
      |              ~^~~~~~~~~~~~~~~~~~~
split.cpp: In function 'void DFS2(int, int, int)':
split.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i=0;k<u && i<graph[node].size();i++)
      |                     ~^~~~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:119:6: warning: unused variable 'small' [-Wunused-variable]
  119 |  int small=a;
      |      ^~~~~
split.cpp:120:6: warning: unused variable 'mid' [-Wunused-variable]
  120 |  int mid=b;
      |      ^~~
split.cpp:121:6: warning: unused variable 'large' [-Wunused-variable]
  121 |  int large=c;
      |      ^~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36