제출 #295622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295622		rqi	Split the Attractions (IOI19_split)	C++14	7 / 100	77 ms	8184 KiB

split

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

typedef vector<int> vi;

#define pb push_back
#define sz(x) (int)(x).size()

const int mx = 100005;
bool SUB1 = 1;
bool SUB2 = 1;
bool SUB3 = 1;
bool SUB4 = 1;
vi adj[mx];
vi res;

vi find_split(int n, int a, int b, int c, vi p, vi q) {
	res = vi(n, 0);
	for(int i = 0; i < sz(p); i++){
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}

	
	
	for(int i = 0; i < n; i++){
		if(sz(adj[i]) > 2) SUB1 = 0;
	}
	if(a != 1) SUB2 = 0;
	if(sz(p) != n-1) SUB3 = 0;
	if(n > 2500 || sz(p) > 5000) SUB4 = 0;

	if(SUB1){
		int A = 0;
		int B = 0;
		int C = 0;
		int cur = 0;
		for(int i = 0; i < n; i++) if(sz(adj[i]) == 1) cur = i;

		int last = -1;

		while(true){
			if(A < a){
				res[cur] = 1;
				A++;
			}
			else if(B < b){
				res[cur] = 2;
				B++;
			}
			else if(C < c){
				res[cur] = 3;
				C++;
			}
			else break;

			if(adj[cur][0] == last){
				if(sz(adj[cur]) == 1) break;
				last = cur;
				cur = adj[cur][1];
			}
			else{
				last = cur;
				cur = adj[cur][0];
			}
		}

		return res;
	}

	if(SUB2){
		vi inComp(n, 0);
		queue<int> q;
		
		cout << b << "\n";
		int B = 0;
		inComp[0] = 1;
		B++;
		q.push(0);
		while(sz(q)){
			int node = q.front();
			q.pop();
			for(auto u: adj[node]) if(!inComp[u] && B < b){
				inComp[u] = 1;
				B++;
				q.push(u);
			}
			if(B == b) break;
		}	

		for(int i = 0; i < n; i++) if(inComp[i]) res[i] = 2;
		for(int i = 0; i < n; i++){
			if(inComp[i] == 0){
				res[i] = 1;
				break;
			}
		}
		for(int i = 0; i < n; i++) if(res[i] == 0) res[i] = 3;

		for(int i = 0; i < n; i++){
			if(res[i] == 1){
				a--;
			}
			else if(res[i] == 2){
				b--;
			}
			else if(res[i] == 3){
				c--;
			}
		}
		assert(a == 0 && b == 0 && c == 0);
	}

	return res;
}

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