Submission #1047481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047481		vjudge1	Split the Attractions (IOI19_split)	C++17	40 / 100	65 ms	25364 KiB

split

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include "split.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int N;
int aa=-1,bb=-1;
int tur[3],per[3];
vector<int>komsu[100000];
vector<int>child[100000];
int sub[100000],par[100000];
int res[100000];
int vis[100000];

pair<int,int> f(int pos){
	sub[pos]=1;
	vis[pos]=1;
	int cur=-2;
	int cur2=-2;
	for(int x:komsu[pos]){
		if(par[pos]==x)continue;
		if(vis[x])continue;
		child[pos].pb(x);
		par[x]=pos;
		pair<int,int> y=f(x);
		if(y==make_pair(-1,-1))return y;
		if(y.fr!=-2)if(cur==-2||sub[y.fr]<sub[cur])
			cur=y.fr;
		if(y.sc!=-2)if(cur2==-2||sub[y.sc]<sub[cur2])
			cur2=y.sc;
		sub[pos]+=sub[x];
	}
	if(cur!=-2){
		if(sub[pos]-sub[cur]>=tur[per[1]]){
			aa=cur;bb=pos;
			return {-1,-1};
		}
	}
	else{
		if(sub[pos]>=tur[per[0]])
			cur=pos;
	}
	if(cur2!=-2){
		if(sub[pos]-sub[cur2]>=tur[per[0]]){
			aa=pos;bb=cur2;
			return {-1,-1};
		}
	}
	else{
		if(sub[pos]>=tur[per[1]])
			cur2=pos;
	}
	return {cur,cur2};
}

int boya(int pos,int renk,int kalan,int kac){
	if(pos==kac)return kalan;
	res[pos]=renk;
	kalan--;
	if(kalan){
		for(int x:child[pos]){
			kalan=boya(x,renk,kalan,kac);
			if(!kalan)break;
		}
	}
	return kalan;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
	N=n;
	tur[0]=a;tur[1]=b;tur[2]=c;
	iota(per,per+3,0);
	sort(per,per+3,[&](const int &x,const int &y){return tur[x]<tur[y];});
	for(int i=0;i<p.size();i++){
		komsu[p[i]].pb(q[i]);
		komsu[q[i]].pb(p[i]);
	}
	int bas=0;
	if(q.size()==n-1){
		for(int i=0;i<n;i++){
			if(komsu[i].size()==1){
				bas=i;break;
			}
		}
	}
	par[bas]=-1;
	if(f(bas)!=make_pair(-1,-1)){
		vector<int>ans;
		for(int i=0;i<N;i++){
			ans.pb(0);
		}
		return ans;
	}
	boya(aa,per[0]+1,tur[per[0]],bb);
	boya(bb,per[1]+1,tur[per[1]],aa);
	int ek=per[2]+1;
	vector<int>ans;
	for(int i=0;i<n;i++){
		if(res[i]){
			ans.pb(res[i]);
		}
		else ans.pb(ek);
	}
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:84:15: 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++){
      |              ~^~~~~~~~~
split.cpp:89:13: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |  if(q.size()==n-1){
      |     ~~~~~~~~^~~~~

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