Submission #1067903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067903		pcc	Split the Attractions (IOI19_split)	C++17	7 / 100	603 ms	1048576 KiB

split

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

using namespace std;

const int mxn = 2e5+10;

vector<int> ans;
int N,A,B,C;
vector<int> paths[mxn];

void dfs(int now,int par,int &cnt,int col){
	ans[now] = col;
	cnt--;
	if(!cnt)return;
	for(auto nxt:paths[now]){
		if(nxt == par)continue;
		dfs(nxt,now,cnt,col);
	}
	return;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	ans = vector<int>(n,0);
	N = n,A = a,B = b,C = c;
	for(int i = 0;i<p.size();i++){
		int a = p[i],b = q[i];
		paths[a].push_back(b);
		paths[b].push_back(a);
	}
	int s = -1,e = -1;
	for(int i = 0;i<N;i++){
		if(paths[i].size() == 1){
			if(s == -1)s = i;
			else e = i;
		}
	}
	if(s == -1)s = 0,e = paths[0][0];
	dfs(s,e,A,1);
	dfs(e,s,B,2);
	for(auto &i:ans)if(!i)i = 3;
	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:26:17: 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++){
      |                ~^~~~~~~~~

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