Submission #726874

#	Time	Username	Problem	Language	Result	Execution time	Memory
726874		alvingogo	Split the Attractions (IOI19_split)	C++14	100 / 100	161 ms	27768 KiB

split

#include "split.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#define fs first
#define sc second
using namespace std;

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int m=p.size();
	vector<vector<int> > e(n);
	for(int i=0;i<m;i++){
		e[p[i]].push_back(q[i]);
		e[q[i]].push_back(p[i]);
	}
	vector<int> ans(n);
	pair<int,int> rk[3]={{a,1},{b,2},{c,3}};
	if(a>b){
		swap(rk[0],rk[1]);
	}
	if(b>c){
		swap(rk[1],rk[2]);
	}
	vector<int> vis(n),vis2(n);
	int flag=0;
	vector<int> sz(n),dep(n);
	function<void(int)> dfs3=[&](int r){
		ans[r]=rk[1].sc;
		vis2[r]=1;
		rk[1].fs--;
		if(rk[1].fs==0){
			return;
		}
		for(auto h:e[r]){
			if(!vis2[h]){
				dfs3(h);
				if(rk[1].fs==0){
					return;
				}
			}
		}
	};
	function<void(int)> dfs2=[&](int r){
		ans[r]=rk[0].sc;
		vis2[r]=1;
		rk[0].fs--;
		if(rk[0].fs==0){
			return;
		}
		for(auto h:e[r]){
			if(dep[h]==dep[r]+1){
				dfs2(h);
				if(rk[0].fs==0){
					return;
				}
			}
		}
	};
	function<int(int,int)> dfs=[&](int r,int d){
		dep[r]=d;
		vis[r]=1;
		sz[r]=1;
		int f3=0;
		int x=1e9;
		vector<pair<int,int> > zz;
		for(auto h:e[r]){
			if(!vis[h]){
				int u=dfs(h,d+1);
				x=min(x,u);
				if(u<dep[r]){
					zz.push_back({sz[h],h});
				}
				sz[r]+=sz[h];
				if(sz[h]>=rk[0].fs){
					f3=1;
				}
				if(flag){
					return (int)1e9;
				}
			}
			else{
				x=min(x,dep[h]);
			}
		}
		if(flag){
			return (int)1e9;
		}
		if(!f3){
			if(sz[r]>=rk[0].fs){
				int u=n-sz[r];
				int f2=0;
				for(int i=0;i<=zz.size();i++){
					if(u>=rk[1].fs){
						dfs2(r);
						for(auto h:e[r]){
							if(dep[h]==dep[r]-1){
								dfs3(h);
								break;
							}
						}
						break;
					}
					if(i==zz.size()){
						f2=1;
						break;
					}
					u+=zz[i].fs;
					dep[zz[i].sc]=-2;
				}
				if(f2){
					
				}
				else{
					for(int j=0;j<n;j++){
						if(ans[j]==0){
							ans[j]=rk[2].sc;
						}
					}
					flag=1;
					return (int)1e9;
				}
			}
		}
		return x;
	};
	dfs(0,0);
	if(flag){
		return ans;
	}
	swap(rk[0],rk[1]);
	fill(vis.begin(),vis.end(),0);
	fill(sz.begin(),sz.end(),0);
	fill(dep.begin(),dep.end(),0);
	dfs(0,0);
	return ans;
}

Compilation message (stderr)

split.cpp: In lambda function:
split.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int i=0;i<=zz.size();i++){
      |                 ~^~~~~~~~~~~
split.cpp:102:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |      if(i==zz.size()){
      |         ~^~~~~~~~~~~

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