제출 #1290977

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

split

#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#define debug(v) cerr << #v << ": " << v << "   ";
#define debugln(v) cerr << #v << ": " << v << endl;


const int MAXN = 1e5+5;

int small, large, meio;
vector<int> res, imp;
vector<int> adj[MAXN];
int pai[MAXN], sz[MAXN];
bool used1[MAXN], used2[MAXN], used3[MAXN];

void dfs_1(int no){
	used1[no] = true;
	sz[no] = 1;
	for(int v : adj[no]){
		if(used1[v]) continue;
		pai[v] = no;
		dfs_1(v);
		sz[no] += sz[v];
	}
}

void dfs_2(int no){
	used2[no] = true;
	// debug(small) debugln(no);
	res[no] = 2;
	for(int v : adj[no]){
		if(used2[v] || small == 0) continue;
		small--;
		dfs_2(v);
	}
}


void dfs_3(int no){
	used3[no] = true;
	// debug(meio) debugln(no);
	res[no] = 3;
	for(int v : adj[no]){
		if(used3[v] || meio == 0) continue;
		meio--;
		dfs_3(v);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	res.resize(n);
	imp.resize(n, 0);
	small = min({a, b, c});
	large = max({a, b, c}); //vai ser galera soltos
	meio = n-small-large; //vai ser o que der

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

	// cerr << "i sz  pai\n";
	vector<pair<int, int>> aux;
	for(int i = 0; i < n; i++){
		// cerr << i << "  " << sz[i] << "  " << pai[i] << "\n";
		aux.push_back({sz[i], i});
	}
	sort(aux.begin(), aux.end());
	int sm = lower_bound(aux.begin(), aux.end(), make_pair(small, 0))->second;
	if(n-sz[sm] < meio) return imp;
	// debugln(sm);
	// debugln(pai[sm]);

	used2[pai[sm]] = true;
	small--;
	dfs_2(sm);

	used3[sm] = true;
	meio--;
	dfs_3(pai[sm]);

	for(int &i : res) if(i==0) i = 1;

	return res;
}

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