Submission #827035

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

split

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

using namespace std;

#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<<'\n';
	x--;
	for(int i=0; i<q[v].size() and x != 0; i++){
		int to = q[v].size();
		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();
	for(int i=0; i<m; i++){
		q[LL[i] + 1].pb(RR[i] + 1);
		q[RR[i] + 1].pb(LL[i] + 1);
	}
	
	int st = 0;
	for(int i=1; i<=n; i++){
		if(q[i].size() == 1){
			st = i;
		}
	}
	if(!st){
		vector<int> ans;
		for(int i=1; i<=A; i++){
			ans.pb(1);
		}
		for(int i=1; i<=B; i++){
		ans.pb(2);
		}
			
		for(int i=1; i<=C; i++){
			ans.pb(3);
		}


		return ans;
	}   
	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;
}




                 

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: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36