Submission #406292

#	Time	Username	Problem	Language	Result	Execution time	Memory
406292		ngrace	Split the Attractions (IOI19_split)	C++14	33 / 100	98 ms	12260 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<pair<int,int>>> adj;
vector<bool> vis;

int dfs(int cur){//on tree
	if(vis[cur]){
		return 0;
	}
	vis[cur]=true;
	int ret=0;
	for(pair<int,int>& it:adj[cur]){
		int sub=dfs(it.first);
		ret+=sub;
		it.second=sub;
	}
	return ret+1;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	if(a==1){//sub 2
		vector<int> answer(n,3);
		vector<vector<int>> lineAdj(n);
		for(int i=0;i<p.size();i++){
			lineAdj[p[i]].push_back(q[i]);
			lineAdj[q[i]].push_back(p[i]);
		}
		stack<int> s;
		s.push(0);
		vector<bool> vis(n);
		while(s.size()>0 && b>0){
			int cur=s.top();
			s.pop();
			if(!vis[cur]){
				vis[cur]=true;
				answer[cur]=2;
				b--;
				for(int& it:lineAdj[cur]){
					s.push(it);
				}
			}
		}
		for(int i=0;i<n;i++){
			if(answer[i]==3){
				answer[i]=1;
				break;
			}
		}
		return answer;
	}
	else if(false){//line case
		vector<vector<int>> lineAdj(n);
		for(int i=0;i<p.size();i++){
			lineAdj[p[i]].push_back(q[i]);
			lineAdj[q[i]].push_back(p[i]);
		}
		int root=0;
		for(int i=0;i<p.size();i++){
			if(lineAdj[i].size()==1){
				root=i;
				break;
			}
		}
		vector<int> par(n);
		par[root]=root;
		int next=lineAdj[root][0];
		int last=root;
		for(int i=1;i<n;i++){
			par[last]=next;
			if(i==n-1){
				break;
			}
			if(lineAdj[next][0]!=last){
				last=next;
				next=lineAdj[next][0];
			}
			else{
				last=next;
				next=lineAdj[next][1];
			}
		}
		vector<int> answer(n);
		int cur=root;
		for(int i=0;i<n;i++){
			if(a>0){
				a--;
				answer[cur]=1;
			}
			else if(b>0){
				b--;
				answer[cur]=2;
			}
			else{
				answer[cur]=3;
			}
			cur=par[cur];
		}
		return answer;
	}
	else if(p.size()==n-1){//tree case
		adj=vector<vector<pair<int,int>>>(n);
		for(int i=0;i<p.size();i++){
			adj[p[i]].push_back({q[i],-1});
			adj[q[i]].push_back({p[i],-1});
		}
		vis=vector<bool>(n);
		dfs(0);
		
		vector<int> answer(n,0);
		bool done=false;
		for(int i=0;i<p.size();i++){
			for(pair<int,int> it:adj[i]){
				int prim=-1,sec=-1,spare=-1;
				if(it.second>=a){
					if(n-it.second>=b){
						prim=1;
						sec=2;
						spare=3;
						done=true;
					}
					else if(n-it.second>=c){
						prim=1;
						sec=3;
						spare=2;
						done=true;
					}
				}
				if(it.second>=b && !done){
					if(n-it.second>=a){
						prim=2;
						sec=1;
						spare=3;
						done=true;
					}
					else if(n-it.second>=c){
						prim=2;
						sec=3;
						spare=1;
						done=true;
					}
				}
				if(it.second>=c && !done){
					if(n-it.second>=a){
						prim=3;
						sec=1;
						spare=2;
						done=true;
					}
					else if(n-it.second>=b){
						prim=3;
						sec=2;
						spare=1;
						done=true;
					}
				}

				if(prim!=-1){
					done=true;
					int primC=(prim==1)?a:((prim==2)?b:c);
					int secC=(sec==1)?a:((sec==2)?b:c);
					vis=vector<bool>(n,false);
					stack<int> s;
					vis[i]=true;
					s.push(it.first);
					while(s.size()>0){
						int cur=s.top();
						s.pop();
						if(!vis[cur]){
							vis[cur]=true;
							if(primC>0){
								primC--;
								answer[cur]=prim;
							}
							else{
								answer[cur]=spare;
							}
							for(pair<int,int> pt:adj[cur]){
								s.push(pt.first);
							}
						}
					}

					vis=vector<bool>(n,false);
					vis[it.first]=true;
					s.push(i);
					while(s.size()>0){
						int cur=s.top();
						s.pop();
						if(!vis[cur]){
							vis[cur]=true;
							if(secC>0){
								secC--;
								answer[cur]=sec;
							}
							else{
								answer[cur]=spare;
							}
							for(pair<int,int> pt:adj[cur]){
								s.push(pt.first);
							}
						}
					}
				}

				if(done){
					break;
				}
			}
			if(done){
				break;
			}
		}
		return answer;
	}
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int i=0;i<p.size();i++){
      |               ~^~~~~~~~~
split.cpp:56:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int i=0;i<p.size();i++){
      |               ~^~~~~~~~~
split.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i=0;i<p.size();i++){
      |               ~^~~~~~~~~
split.cpp:103:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |  else if(p.size()==n-1){//tree case
      |          ~~~~~~~~^~~~~
split.cpp:105:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int i=0;i<p.size();i++){
      |               ~^~~~~~~~~
split.cpp:114:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |   for(int i=0;i<p.size();i++){
      |               ~^~~~~~~~~
split.cpp:218:1: warning: control reaches end of non-void function [-Wreturn-type]
  218 | }
      | ^

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