Submission #406195

#	Time	Username	Problem	Language	Result	Execution time	Memory
406195		ngrace	Split the Attractions (IOI19_split)	C++14	7 / 100	88 ms	9256 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(true){//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:26:16: 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<p.size();i++){
      |               ~^~~~~~~~~
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<p.size();i++){
      |               ~^~~~~~~~~
split.cpp:73:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |  else if(p.size()==n-1){//tree case
      |          ~~~~~~~~^~~~~
split.cpp:75:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i=0;i<p.size();i++){
      |               ~^~~~~~~~~
split.cpp:84:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int i=0;i<p.size();i++){
      |               ~^~~~~~~~~

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