Submission #1047489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047489		NotLinux	Split the Attractions (IOI19_split)	C++17	7 / 100	28 ms	8280 KiB

split

#include <bits/stdc++.h>
#include "split.h"
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
const int N = 1e5 + 7;
vector < int > graph[N] , color;
int cur_color = 1;
int dfs(int node , int sayac){
	if(sayac == 0)return node;
	// cout << "dfs : " << node << " , " << cur_color << endl;
	color[node] = cur_color;
	int ret = -1;
	for(auto itr : graph[node]){
		if(color[itr] == -1){
			ret = dfs(itr , sayac - 1);
			break;
		}
	}
	return ret;
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	color.assign(n , -1);
	for(int i = 0;i<sz(p);i++){
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}
	bool bl = 1;
	for(int i = 0;i<n;i++){
		bl &= sz(graph[i]) <= 2;
	}
	if(bl){
		int root = 0;
		for(int i = 0;i<n;i++){
			if(sz(graph[i]) == 1){
				root = i;
				break;
			}
		}
		// cout << "root0 : " << root << endl;
		root = dfs(root , a);
		cur_color++;
		// cout << "root1 : " << root << endl;
		root = dfs(root , b);
		cur_color++;
		// cout << "root2 : " << root << endl;
		root = dfs(root , c);
	}
	return color;
}

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