제출 #1290780

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290780		Sofiatpc	Split the Attractions (IOI19_split)	C++20	0 / 100	589 ms	1114112 KiB

split

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

using namespace std;

const int MAXN = 1e5+5;
vector<int> adj[MAXN], res;
int qtdb[MAXN], qtdc[MAXN], sub[MAXN], A,B,C,N, marc[3], atual;

void dfsIni(int s, int p){
	sub[s] = 1; qtdb[s] = 0; qtdc[s] = 0;
	for(int i = 0; i < adj[s].size(); i++)
		if(adj[s][i] != p){
			dfsIni(adj[s][i],s);
			sub[s] += sub[adj[s][i]];
			qtdb[s] += qtdb[adj[s][i]];
			qtdc[s] += qtdc[adj[s][i]];
		}
	if(sub[s] == B)qtdb[s]++;
	if(sub[s] == C)qtdc[s]++;
}

void marcar(int s, int p){
	res[s] = atual;
	for(int i = 0; i < adj[s].size(); i++)
		if(adj[s][i] != p && res[adj[s][i]] == 0)marcar(adj[s][i],s);
}

int girar(int s, int p){
	for(int i = 0; i < adj[s].size(); i++){
		if(sub[adj[s][i]] == A && (qtdb[s]-qtdb[adj[s][i]]-(sub[s] == B) > 0 || qtdc[s]-qtdc[adj[s][i]]-(sub[s] == C) > 0)){
			atual = marc[0]; marcar(adj[s][i],s);
			int cur = s, pai = -1;
			int temp = 0;
			while(cur == s || (sub[cur] != B && sub[cur] != C) ){
				for(int i = 0; i < adj[s].size(); i++){
					if(adj[s][i] != pai && res[adj[s][i]] == 0 && (qtdb[adj[s][i]] > 0 || qtdc[adj[s][i]] > 0)){pai = cur; cur = adj[s][i]; break;}
				}
				temp++;
				assert(temp <= N);
			}
			if(sub[cur] == B){atual = marc[1]; marcar(cur,pai); atual = marc[2]; marcar(s,-1);}
			else {atual = marc[2]; marcar(cur,pai); atual = marc[1]; marcar(s,-1);}
			return adj[s][i];
		}
	}

	for(int i = 0; i < adj[s].size(); i++)
		if(adj[s][i] != p){
			 qtdb[s] -= qtdb[adj[s][i]]+(sub[s] == B); qtdc[s] -= qtdc[adj[s][i]]+(sub[s] == C); sub[s] -= sub[adj[s][i]];
			 sub[adj[s][i]] += sub[s]; qtdb[adj[s][i]] += qtdb[s]+(sub[adj[s][i]]==B); qtdc[adj[s][i]] += qtdc[s]+(sub[adj[s][i]]==C);
			 int x = girar(adj[s][i],s);
			 if(x != -1)return x;
			 qtdb[adj[s][i]] -= qtdb[s]+(sub[adj[s][i]]==B); qtdc[adj[s][i]] -= qtdc[s]+(sub[adj[s][i]]==C); sub[adj[s][i]] -= sub[s];
			 sub[s] += sub[adj[s][i]]; qtdb[s] += qtdb[adj[s][i]]+(sub[s] == B); qtdc[s] += qtdc[adj[s][i]]+(sub[s] == C);
		}
	return -1;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	res.resize(n); N = n;

	for(int i = 0; i < n; i++)adj[i].clear();

	for(int i = 0; i < p.size(); i++){
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}

	marc[0] = 1; marc[1] = 2; marc[2] = 3; A = a; B = b; C = c;
	dfsIni(0,-1);
	int x = girar(0,-1);
	if(x != -1)return res;

	marc[0] = 2; marc[1] = 1; marc[2] = 3; A = b; B = a; C = c;
	dfsIni(0,-1);
	x = girar(0,-1);
	if(x != -1)return res;

	marc[0] = 3; marc[1] = 2; marc[2] = 1; A = c; B = b; C = a;
	dfsIni(0,-1);
	x = girar(0,-1);
	if(x != -1)return res;

	if(x == -1){
		for(int i = 0; i < n; i++)res[i] = 0;
	}
	return res;
}

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