Submission #1075625

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

split

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


using namespace std;

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

void dfs(int k,int length){
	if(dist[k] != -1)return;
	dist[k] = length;

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