Submission #602806

#	Time	Username	Problem	Language	Result	Execution time	Memory
602806		chirathnirodha	Split the Attractions (IOI19_split)	C++17	40 / 100	565 ms	1048576 KiB

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define P push 
#define I insert
vector<int> edges[200000];
int n,m,a,b,c;
int parent[200000];
int subsiz[200000];
vector<int> ans;
void dfs(int x){
	subsiz[x]=1;
	for(int i=0;i<edges[x].size();i++){
		int y=edges[x][i];
		if(y==parent[x])continue;
		parent[y]=x;
		dfs(y);
		subsiz[x]+=subsiz[y];
	}
}
void colouring(int toall,int nd,int ucol, int unum,int dcol,int dnum){
	for(int i=0;i<n;i++)ans[i]=toall;
	queue<int> q;q.P(nd);
	ans[nd]=dcol;dnum--;
	while(!q.empty() && dnum>0){
		int cur=q.front();q.pop();
		for(int i=0;i<edges[cur].size();i++){
			int y=edges[cur][i];
			if(y==parent[cur])continue;
			if(dnum<=0)break;
			ans[y]=dcol;dnum--;
			q.P(y);
		}
	}
	bool visited[n];memset(visited,false,sizeof(visited));
	visited[parent[nd]]=true;ans[parent[nd]]=ucol;unum--;
	queue<int> q1;q1.P(parent[nd]);
	while(!q1.empty() && unum>0){
		int cur=q1.front();q1.pop();
		for(int i=0;i<edges[cur].size();i++){
			int y=edges[cur][i];
			if(y==nd || visited[y])continue;
			if(unum<=0)break;
			q1.P(y);
			ans[y]=ucol;unum--;
			visited[y]=true;
		}
	}
}
void Subtask_1_3(){
	parent[0]=0;
	dfs(0);
	for(int i=0;i<n;i++){
		if(subsiz[i]>=a){
			if(n-subsiz[i]>=b){colouring(3,i,2,b,1,a);break;}
			if(n-subsiz[i]>=c){colouring(2,i,3,c,1,a);break;}
		}
		if(subsiz[i]>=b){
			if(n-subsiz[i]>=a){colouring(3,i,1,a,2,b);break;}
			if(n-subsiz[i]>=c){colouring(1,i,3,c,2,b);break;}
		}
		if(subsiz[i]>=c){
			if(n-subsiz[i]>=b){colouring(1,i,2,b,3,c);break;}
			if(n-subsiz[i]>=a){colouring(2,i,1,a,3,c);break;}
		}
	}
	return;
}
void Subtask_2(){
	bool visited[n];memset(visited,false,sizeof(visited));
	for(int i=0;i<n;i++)ans[i]=3;
	visited[0]=true;ans[0]=2;b--;
	queue<int> q;q.P(0);
	while(!q.empty() && b>0){
		int cur=q.front();q.pop();
		for(int i=0;i<edges[cur].size();i++){
			int y=edges[cur][i];
			if(visited[y])continue;
			if(b<=0)break;
			visited[y]=true;
			ans[y]=2;b--;
			q.P(y);
		}
	}
	for(int i=0;i<n;i++)if(visited[i]==false){ans[i]=1;break;}
	return;
}
vector<int> find_split(int N,int A,int B,int C,vector<int> p,vector<int> q) {
	n=N;a=A;b=B;c=C;m=p.size();
	for(int i=0;i<n;i++)ans.PB(0);
	if(a!=1 && m==n)m--;
	for(int i=0;i<m;i++){
		edges[p[i]].PB(q[i]);
		edges[q[i]].PB(p[i]);
	}
	if(a==1)Subtask_2();
	else Subtask_1_3();
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'void dfs(int)':
split.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i=0;i<edges[x].size();i++){
      |              ~^~~~~~~~~~~~~~~~
split.cpp: In function 'void colouring(int, int, int, int, int, int)':
split.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(int i=0;i<edges[cur].size();i++){
      |               ~^~~~~~~~~~~~~~~~~~
split.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i=0;i<edges[cur].size();i++){
      |               ~^~~~~~~~~~~~~~~~~~
split.cpp: In function 'void Subtask_2()':
split.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for(int i=0;i<edges[cur].size();i++){
      |               ~^~~~~~~~~~~~~~~~~~

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