제출 #1047641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1047641		NotLinux	Split the Attractions (IOI19_split)	C++17	7 / 100	33 ms	10660 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 = 2e5 + 7;
vector < int > graph[N] , color;
int cur_color = 1;
int dfs1(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 = dfs1(itr , sayac - 1);
			break;
		}
	}
	return ret;
}
int subt[N] , tin[N] , tout[N];
vector < int > tour;
int dfs2(int node , int past){
	subt[node] = 1;
	tour.push_back(node);
	tin[node] = sz(tour) - 1;
	for(auto itr : graph[node]){
		if(subt[itr] == -1){
			subt[node] += dfs2(itr , node);
		}
	}
	tout[node] = sz(tour) - 1;
	return subt[node];
}
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 = dfs1(root , a);
		cur_color++;
		// cout << "root1 : " << root << endl;
		root = dfs1(root , b);
		cur_color++;
		// cout << "root2 : " << root << endl;
		root = dfs1(root , c);
	}
	else{
		memset(subt , -1 , sizeof(subt));
		dfs2(0 , 0);
		int suf[n+1][3];
		memset(suf , 0 , sizeof(suf));
		for(int i = n-1;i>=0;i--){
			suf[i][0] = suf[i+1][0] + (subt[tour[i]] == a);
			suf[i][1] = suf[i+1][1] + (subt[tour[i]] == b);
			suf[i][2] = suf[i+1][2] + (subt[tour[i]] == c);
		}
		int query[3] = {a , b, c};
		vector < int > perm = {0 , 1 , 2};
		// cout << "tour : ";for(auto itr : tour)cout << itr << " ";cout << endl;
		do{
			// cout << "colors : ";for(auto itr : perm)cout << itr << " ";cout << endl;
			int fa = query[perm[0]] , fb = query[perm[1]];
			for(int i = 0;i<n;i++){
				if(subt[tour[i]] == fa and suf[tout[tour[i]]+1][perm[1]] > 0){
					color.assign(n , perm[2] + 1);
					// cout << "root for " << perm[0] + 1 << " : " << tour[i] << endl;
					for(int j = tin[tour[i]];j<=tout[tour[i]];j++){
						color[tour[j]] = perm[0] + 1;
					}
					int root = -1;
					for(int j = tout[tour[i]] + 1;j<n;j++){
						if(subt[tour[j]] == fb){
							root = tour[j];
							break;
						}
					}
					// cout << "root for " << perm[1] + 1 << " : " << root << endl;
					for(int j = tin[root];j<=tout[root];j++){
						color[tour[j]] = perm[1] + 1;
					}
					return color;
				}
				// cout << tour[i] << " : " << subt[tour[i]] << endl;
				if(subt[tour[i]] == (fa + fb) and (suf[tin[tour[i]]][perm[1]] - suf[tout[tour[i]]+1][perm[1]]) > 0){
					color.assign(n , perm[2] + 1);
					int root = -1;
					for(int j = tin[tour[i]];j<=tout[tour[i]];j++){
						if(subt[tour[j]] == fb){
							root = tour[j];
							break;
						}
					}
					for(int j = tin[root];j<=tout[root];j++){
						color[tour[j]] = perm[1] + 1;
					}
					// cout << "root for " << perm[0] + 1 << " : " << tour[i] << endl;
					for(int j = tin[tour[i]];j<=tout[tour[i]];j++){
						if(color[tour[j]] == 0)color[tour[j]] = perm[0] + 1;
					}
					// cout << "root for " << perm[1] + 1 << " : " << root << endl;
					return color;
				}
			}
		} while(next_permutation(all(perm)));
		color.assign(n , 0);
	}
	return color;
}

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