제출 #1228441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228441		walizamanee	Split the Attractions (IOI19_split)	C++20	100 / 100	80 ms	22600 KiB

split

#include<bits/stdc++.h>
#include "split.h"
using namespace std;

int one , two , three , ek , dui , tin , siz[100001] , m , vis[100001] , par[100001] , uttor , ans;
int depth[100001] , upore[100001] , heredepth , here , chek , baki , avoid[100001] , unoo , doss , tress;
int typp , bakk;
vector<int> adj[100001] , chs ;
set<int> uno , dos , tres , chose; // tres biggest


void dfs( int me ) {
	siz[me] = 1;
	vis[me] = 1;
	for( int z = 0; z < (int)adj[me].size(); z++ ) {
		if( vis[adj[me][z]] == 0 ) {
			par[adj[me][z]] = me;
			depth[adj[me][z]] = depth[me] + 1;
			upore[adj[me][z]] = depth[me] + 1;
			dfs( adj[me][z] );
			upore[me] = min( upore[me] , upore[adj[me][z]] );
			siz[me] += siz[adj[me][z]];
		}
		else upore[me] = min( upore[me] , depth[adj[me][z]] );
	}
	if( siz[me] >= ek && siz[me] <= dui ) uttor = me;
	else if( siz[me] > dui ) {
		if( depth[me] > heredepth ) {
			heredepth = depth[me];
			here = me;
		}
	} 
}

void makeans( int me , int typ ) {
	avoid[me] = 1;
	if( baki > 0 ) {
			if( typ == 1 ) {
				uno.insert(me);
				baki--;
			}
			else{
				dos.insert(me);
				baki--;
			}
	}
    for( int z = 0; z < (int)adj[me].size(); z++ ) {
		if( (depth[adj[me][z]] - depth[me]) == 1 && avoid[adj[me][z]] != 1 ) {
			if( baki > 0 ) {
			makeans( adj[me][z] , typ );
			}
		}
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	uttor = -1;
	chek = 0;
	one = min(a , b);
	one = min( one , c );
	three = max( a , b );
	three = max( three , c );
	two = n - (one + three);
	ek = one;
	dui = (two + three);
	if( a == one ) {
		unoo = 1;
		doss = 2;
		tress = 3;
		if( b == three ) swap( doss , tress );
	}
	else if( b == one ) {
		unoo = 2;
		doss = 1;
		tress = 3;
		if( a == three ) swap( doss , tress );
	}
	else{
		unoo = 3;
		doss = 1;
		tress = 2;
		if( a == three ) swap( doss , tress );
	}

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

	dfs( 0 );
	if( uttor == -1 ) {
		int bortoman = ( n - siz[here] );
		chs.push_back(0);
		for( int z = 0; z < (int)adj[here].size(); z++ ) {
			if( depth[adj[here][z]] - depth[here] == 1 ) {
				if( bortoman < one && upore[adj[here][z]] < depth[here] ) {
					chs.push_back(adj[here][z]);
					bortoman += siz[adj[here][z]];
				}
			}
		}
		if( bortoman < one ) chek = -1;
		if( bortoman >= two ) {
			typp = 2;
			baki = two;
		}
		else{
			typp = 1;
			baki = one;
		}
		for( int z = 0; z <= n; z++ ) avoid[z] = 0;
		avoid[here] = 1;
		for( int z = 0; z < (int)chs.size(); z++ ) {
			if( baki > 0 ) makeans( chs[z] , typp );
		}
		avoid[here] = 0;
		if( typp == 1 ) {
			typp = 2;
			baki = two;
		}
		else{
			typp = 1;
			baki = one;
		}
		makeans( here , typp );
	}
	else{
		if( siz[uttor] >= two ) {
			typp = 2;
			baki = two;
		}
		else{
			typp = 1;
			baki = one;
		}
		makeans( uttor , typp );
		if( typp == 1 ) {
			typp = 2;
			baki = two;
		}
		else{
			typp = 1;
			baki = one;
		}
		makeans( 0 , typp );
	}
	for( int z = 0; z < n; z++ ) {
		if( avoid[z] == 0 ) tres.insert(z);
	}
	vector<int> finalans(n);
    if( chek == -1 ) for( int z = 0; z < n; z++ ) finalans[z] = 0;
	else{
		for( auto it = uno.begin(); it != uno.end(); ++it ) {
			finalans[*it] = unoo;
		}
		for( auto it = dos.begin(); it != dos.end(); ++it ) {
			finalans[*it] = doss;
		}
		for( auto it = tres.begin(); it != tres.end(); ++it ) {
			finalans[*it] = tress;
		}
	}
	return finalans;

}

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