제출 #1151862

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151862		Pacybwoah	Split the Attractions (IOI19_split)	C++20	40 / 100	1987 ms	21776 KiB

split

#include "split.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
#include<utility>
#include<random>
#include<chrono>
using namespace std;
namespace{
	vector<int> ord;
	vector<int> sz, pa, vis;
	vector<vector<int>> graph, ng;
	int cnt = 0;
	void dfs(int node, int parent){
		// << node <<  " " << parent << "\n";
		sz[node] = 1;
		pa[node] = parent;
		ord[cnt] = node;
		cnt++;
		vis[node] = 1;
		for(auto &x: graph[node]){
			//cout << x << " " << vis[x] << " " << parent << "\n";
			if(vis[x]) continue;
			if(x == parent) continue;
			dfs(x, node);
			sz[node] += sz[x];
			ng[node].push_back(x);
			ng[x].push_back(node);
		}
	}
	void dfs_ban(int node, int parent, int ban){
		ord[cnt] = node;
		cnt++;
		for(auto &x: ng[node]){
			if(x == parent || x == ban) continue;
			dfs_ban(x, node, ban);
		}
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> ans(n);
	sz.resize(n);
	graph.resize(n);
	pa.resize(n);
	vis.resize(n);
	ord.resize(n);
	ng.resize(n);
	for(int i = 0; i < (int)p.size(); i++){
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}
	dfs(0, 0);
	if(a == 1){
		//for(auto x: ord) cout << x << ' ';
		assert((int)ord.size() == n);
		for(int i = 0; i < b; i++) ans[ord[i]] = 2;
		for(int i = b; i < b + c; i++) ans[ord[i]] = 3;
		ans[ord[n - 1]] = 1;
		return ans;
	}
	int na = 1, nb = 2, nc = 3;
	if(a > b){
		swap(a, b);
		swap(na, nb);
	}
	if(b > c){
		swap(b, c);
		swap(nb, nc);
	}
	if(a > b){
		swap(a, b);
		swap(na, nb);
	}
	auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
	mt19937_64 mt(seed);
	auto st = clock();
	vector<int> old, pos(n);
	uniform_int_distribution<int> dis(0, n - 1);
	while(float(clock() - st) / CLOCKS_PER_SEC < 1.9){
		vector<vector<int>>().swap(ng);
		ng.resize(n);
		cnt = 0;
		for(int i = 0; i < n; i++) shuffle(graph[i].begin(), graph[i].end(), mt);
		fill(ord.begin(), ord.end(), 0);
		fill(vis.begin(), vis.end(), 0);
		int node = dis(mt);
		//cout << node << "\n";
		dfs(node, node);
		cnt = 0;
		//for(auto &x: ord) cout << x << " ";
		old = ord;
		for(int i = 0; i < n; i++) pos[ord[i]] = i;
		fill(ord.begin(), ord.end(), 0);
		for(int i = 0; i < n; i++){
			if(sz[i] >= a && n - sz[i] >= b){
				dfs_ban(pa[i], pa[i], i);
				for(int j = pos[i]; j < pos[i] + a; j++) ans[old[j]] = na;
				for(int j = 0; j < b; j++) ans[ord[j]] = nb;
				for(int j = 0; j < n; j++) if(ans[j] == 0) ans[j] = nc;
				return ans;
			}
			if(sz[i] >= b && n - sz[i] >= a){
				dfs_ban(pa[i], pa[i], i);
				for(int j = pos[i]; j < pos[i] + b; j++) ans[old[j]] = nb;
				for(int j = 0; j < a; j++) ans[ord[j]] = na;
				for(int j = 0; j < n; j++) if(ans[j] == 0) ans[j] = nc;
				return ans;
			}
		}
	}
	return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run split.cpp grader.cpp

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