Submission #827095

#	Time	Username	Problem	Language	Result	Execution time	Memory
827095		vjudge1	Split the Attractions (IOI19_split)	C++17	29 / 100	394 ms	1048576 KiB

split

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

using namespace std;
//asdasd
#define all(x) x.begin(), x.end()
#define pb push_back
#define ll long long
#define vout(v) for(int i=0; i<v.size(); i++) cout<<v[i]<<' '
#define pii pair<int, int>
#define ff first
#define ss second
#define mp make_pair
    
vector<int> q[200100];
int sz[200100];
int res[200100], p[200100];

void dfs1(int v){
	sz[v] = 1;
	for(int i=0; i<q[v].size(); i++){
		int to = q[v][i];
		if(to == p[v]) continue;
		p[to] = v;
		dfs1(to);
		sz[v] += sz[to];
	}	
}

int dfs2(int v, int x, int c){
	res[v] = c;
	//cout<<v<<' '<<x<<'\n';
	x--;
	for(int i=0; i<q[v].size() and x != 0; i++){
		int to = q[v][i];
		if(p[v] == to) continue;
		p[to] = v;
		x = dfs2(to, x, c);
	}
	return x;
}

vector<int> find_split(int n, int A, int B, int C, vector<int> LL, vector<int> RR){
	int m = LL.size();
	if(n == m) m--;
	for(int i=0; i<m; i++){
		q[LL[i] + 1].pb(RR[i] + 1);
		q[RR[i] + 1].pb(LL[i] + 1);
	}
	if(A == 1){
		for(int i=1; i<=n; i++){
			q[i].clear();
		}
		m = LL.size();
		for(int i=0; i<m; i++){
			q[LL[i] + 1].pb(RR[i] + 1);
			q[RR[i] + 1].pb(LL[i] + 1);
		}
		p[1] = 0;
		dfs2(1, B, 2);
		vector<int> ans(n);
		for(int i=1; i<=n; i++){
			if(res[i] == 0){
				if(C){
					C--;
					res[i] = 3;
				}
				else{
					res[i] = 1;
				}
			}
			ans[i-1] = res[i];
		}
		return ans;

	}
	//cout<<"asdasdasdasd\n\n\n\n\n";
	if(n == m+1){
		p[1] = 0;
		dfs1(1);
		vector<pii> qq;
		qq.pb(mp(A, 1));
		qq.pb(mp(B, 2));
		qq.pb(mp(C, 3));
		sort(all(qq));
		pii d1=qq[0], d2=qq[1];
		int ok=0;
		for(int i=2; i<=n; i++){
			//cout<<sz[i]<<' ';
			if(min(d1.ff, d2.ff) <= min(sz[i], n-sz[i]) and max(d1.ff, d2.ff) <= max(sz[i], n-sz[i])){
				ok=i;
				break;
			}
		}
		vector<int> ans(n, 0);
		//cout<<ok<<"\n\n\n\n";
		if(!ok){
			return ans;
		}
		int t = p[ok];
		if(sz[ok] > n - sz[ok]){
			p[ok] = t;
			dfs2(ok, d2.ff, d2.ss);
			p[t] = ok;
			dfs2(t, d1.ff, d1.ss);
		}
		else{
		//cout<<"asdsad";
			p[ok] = t;
			dfs2(ok, d1.ff, d1.ss);
			p[t] = ok;
			dfs2(t, d2.ff, d2.ss);
			//cout<<d2.ff<<'\n';
		}
		for(int i=1; i<=n; i++){
			if(res[i] == 0) res[i] = qq[2].ss;
			ans[i-1] = res[i];
		}
		
		return ans;

	}
	int st = 0;
	for(int i=1; i<=n; i++){
		if(q[i].size() == 1){
			st = i;
		}
	}   
	p[st] = 0;
	dfs1(st);
	vector<int> ans(n);
	for(int i=1; i<=n; i++){
		//cout<<sz[i]<<'\n';
		if(sz[i] <= A){
			ans[i-1] = 1;
		}
		else if(sz[i] <= A + B){
			ans[i-1] = 2;
		}
		else{
			ans[i-1]=3; 
		}
	}	
	return ans;

	return ans;
}




                 








                 

Compilation message (stderr)

split.cpp: In function 'void dfs1(int)':
split.cpp:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0; i<q[v].size(); i++){
      |               ~^~~~~~~~~~~~
split.cpp: In function 'int dfs2(int, int, int)':
split.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |  for(int i=0; i<q[v].size() and x != 0; i++){
      |               ~^~~~~~~~~~~~

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