제출 #1290801

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290801		Sofiatpc	Split the Attractions (IOI19_split)	C++20	0 / 100	576 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)){
			//cerr<<s<<" "<<adj[s][i]<<" "<<sub[s]<<" "<<sub[adj[s][i]]<<" | "<<A<<" "<<B<<" "<<C<<"\n";
			//cerr<<qtdb[s]<<" "<<qtdb[adj[s][i]]<<" "<<qtdc[s]<<" "<<qtdc[adj[s][i]]<<"\n";
			atual = marc[0]; marcar(adj[s][i],s);
			int cur = s, pai = -1;
			while(cur == s || (sub[cur] != B && sub[cur] != C) ){
				//cerr<<cur<<"\n";
				for(int j = 0; j < adj[cur].size(); j++){
					//cerr<<qtdb[adj[cur][j]]<<" "<<qtdc[adj[cur][j]]<<"\n";
					if(adj[cur][j] != pai && res[adj[cur][j]] == 0 && (qtdb[adj[cur][j]] > 0 || qtdc[adj[cur][j]] > 0))
						{pai = cur; cur = adj[cur][j]; break;}
				}
			}
			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){
			int bs = qtdb[s], cs = qtdc[s], ss = sub[s];
			int bviz = qtdb[adj[s][i]], cviz = qtdc[adj[s][i]],sviz = sub[adj[s][i]];
			 qtdb[s] -= qtdb[adj[s][i]]+(sub[s] == B); qtdc[s] -= qtdc[adj[s][i]]+(sub[s] == C);
			 sub[s] -= sub[adj[s][i]];
			 qtdb[s] += (sub[s] == B); qtdc[s] += (sub[s] == C);

			 qtdb[adj[s][i]] -= (sub[adj[s][i]] == B); qtdc[adj[s][i]] -= (sub[adj[s][i]] == C);
			 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[s] = bs; qtdc[s] =cs; sub[s] = ss; qtdb[adj[s][i]] = bviz; qtdc[adj[s][i]] = cviz; sub[adj[s][i]] = sviz;
		}
	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