Submission #1075560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075560		mindiyak	Split the Attractions (IOI19_split)	C++14	0 / 100	610 ms	1048576 KiB

split

#include "split.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>


using namespace std;

vector<vector<int>> paths(1e5+5);

int len = 0,pos = 0;

void dfs(int k,int m,int length){
	if(length > len){
		pos = k;
		length = len;
	}
	for(int l:paths[k]){
		if(l==m)continue;
		dfs(l,k,length+1);
	}
}


vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	int sub1 = 1;
	for(int i=0;i<p.size();i++){
		paths[p[i]].push_back(q[i]);
		paths[q[i]].push_back(p[i]);
	}
	for(int i=0;i<n;i++)if(paths[i].size() > 2)sub1 = 0;

	vector<int> temp = {a,b,c};
	sort(temp.begin(),temp.end());
	a = temp[0];b = temp[1];c = temp[2];

	if(sub1 == 1){
		dfs(0,-1,1);
		queue<int> pq;
		pq.push(pos);
		vector<int> ans(n,0);
		while(a > 0){
			int k = pq.front();pq.pop();
			if(ans[k] != 0)continue;
			ans[k] = 1;
			a--;
			for(int l:paths[k]){
				pq.push(l);
			}
		}
		while(b > 0){
			int k = pq.front();pq.pop();
			if(ans[k] != 0)continue;
			ans[k] = 2;
			b--;
			for(int l:paths[k]){
				pq.push(l);
			}
		}
		for(int i=0;i<n;i++){
			if(ans[i] == 0){
				ans[i] = 3;
			}
		}
		return ans;
	}

	if(a == 1){
		queue<int> pq;
		pq.push(0);
		vector<int> ans(n,0);
		while(b > 0){
			int k = pq.front();pq.pop();
			if(ans[k] != 0)continue;
			ans[k] = 2;
			b--;
			for(int l:paths[k]){
				pq.push(l);
			}
		}
		for(int i=0;i<n;i++){
			if(ans[i] == 0){
				ans[i] = 1;
				break;
			}
		}
		for(int i=0;i<n;i++){
			if(ans[i] == 0){
				ans[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:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:34:27: warning: control reaches end of non-void function [-Wreturn-type]
   34 |  vector<int> temp = {a,b,c};
      |                           ^

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