제출 #285182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285182		cookiedoth	Split the Attractions (IOI19_split)	C++14	40 / 100	117 ms	15252 KiB

split

/*

Code for problem B by cookiedoth
Generated 28 Aug 2020 at 01.11 PM


СТРОИМ КОММУНИЗМ РАБОТЯГИ!
 
                                    ╦═╩═╦═╩═█
                          ████▄▄▄═╦═╩═╦═╩═╦═█
                  ████████████████▄▄╦═╩═╦═╩═█
█═╦═╩═╦▄████████████████▀▀▀▀█████████▄╦═╩═╦═█
█═╩═╦═████████████████████▄═╦▀█████████═╦═╩═█
█═╦═▄██████████▀╩═╦═╩▄██████▄═╦▀████████▄═╦═█
█═╩═█████████▀╩═╦═╩═█████████▄╩═╦████████═╩═█
█═╦█████████▄═╦═╩═╦═▀█████████╦═╩═████████╦═█
█═╩███████████▄▄██▄═╦═▀████████═╦═████████╩═█
█═██████████████████▄═╦═▀█████▀═╩═█████████═█
█═████████████████████▄═╦═▀███╩═╦═█████████═█
█═╦████████████▀╩▀██████▄═╦═▀═╦═╩█████████╦═█
█═╩█████████▀═╩═╦═╩▀▀███▀▀╩═╦═╩═██████████╩═█
█═╦═██████▀═╦═▄▄█▄▄═╩═╦═╩═╦═╩═╦═╩▀███████═╦═█
█═╩═▀████═╩═▄█████████▄▄▄▄████▄═╦═╩█████▀═╩═█
█═╦═╩═██████████████████████████▄═▄████═╩═╦═█
█═╩═╦═╩▀█████████████████████████████▀╩═╦═╩═█
█═╦═╩═╦═╩▀▀███████████████████████▀▀╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═▀▀▀███████████████▀▀▀═╩═╦═╩═╦═╩═█
█═╦═╩═╦═╩═╦═╩═╦═╩═▀▀▀▀▀▀▀▀▀═╩═╦═╩═╦═╩═╦═╩═╦═█
█═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═╦═╩═█
█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄█

=_=
¯\_(ツ)_/¯
o_O

*/

#include "split.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#include <random>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define length(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

const int mx = 1e5 + 228;
vector<vector<int> > g;
vector<int> ans;
int n, used[mx], a, b, c, timer;

void dfs(int v) {
	used[v] = 1;
	if (timer < b) {
		ans[v] = 2;
	} else {
		if (timer < a + b) {
			ans[v] = 1;
		} else {
			ans[v] = 3;
		}
	}
	timer++;
	for (auto v1 : g[v]) {
		if (used[v1] == 0) {
			dfs(v1);
		}
	}
}

void solve_dfs() {
	for (int i = 0; i < n; ++i) {
		if (g[i].size() == 1) {
			dfs(i);
			return;
		}
	}
	dfs(0);
}

int sz[mx], par[mx];

void dfs(int v, int pv) {
	par[v] = pv;
	sz[v] = 1;
	for (auto v1 : g[v]) {
		if (v1 != pv) {
			dfs(v1, v);
			sz[v] += sz[v1];
		}
	}
}

void build_cmp(int v, int pv, int &v_cnt, int clr) {
	v_cnt--;
	ans[v] = clr;
	for (auto v1 : g[v]) {
		if (v1 != pv && v_cnt) {
			build_cmp(v1, v, v_cnt, clr);
		}
	}
}

void solve_tree() {
	// cerr << "solve_tree" << endl;
	dfs(0, 0);
	for (int i = 1; i < n; ++i) {
		if (sz[i] >= a && (n - sz[i]) >= b) {
			fill(all(ans), 3);
			build_cmp(i, par[i], a, 1);
			build_cmp(par[i], i, b, 2);
			return;
		}
		if (sz[i] >= b && (n - sz[i]) >= a) {
			fill(all(ans), 3);
			build_cmp(i, par[i], b, 2);
			build_cmp(par[i], i, a, 1);
			return;
		} 
	}
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
	n = _n;
	a = _a;
	b = _b;
	c = _c;
	g.resize(n);
	int m = p.size();
	for (int i = 0; i < m; ++i) {
		g[p[i]].push_back(q[i]);
		g[q[i]].push_back(p[i]);
	}
	ans.resize(n);
	if (m == n - 1) {
		solve_tree();
	} else {
		solve_dfs();
	}
	return ans;
}

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