제출 #452069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
452069		flappybird	Split the Attractions (IOI19_split)	C++14	100 / 100	216 ms	25648 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
typedef int ll;
#define MAX 101010
ll N;
ll num[MAX], prt[MAX];
ll color[MAX];
vector<ll> adj[MAX], tree[MAX];
ll vis[MAX];
ll cnt = 0;
ll ord[MAX];
ll memo[MAX];
ll arr[MAX];
ll split[2][MAX];
ll dfs(ll x = 0, ll p = -1) {
	ord[x] = ++cnt;
	prt[x] = p;
	num[x] = 1;
	vis[x] = 1;
	ll ret = ord[x];
	for (auto v : adj[x]) {
		if (v == p) continue;
		if (vis[v]) {
			ret = min(ret, ord[v]);
			continue;
		}
		ret = min(dfs(v, x), ret);
		num[x] += num[v];
	}
	return memo[x] = ret;
}
void chk(ll x, ll p, ll c) {
	arr[x] = c;
	for (auto v : tree[x]) {
		if (v == p) continue;
		chk(v, x, c);
	}
}
void dfs2(ll x, ll p, ll c) {
	split[c][x] = ++cnt;
	vis[x] = 1;
	for (auto v : adj[x]) {
		if (v == p || arr[v] != c) continue;
		if (vis[v]) continue;
		dfs2(v, x, c);
	}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> res;
	N = n;
	res.resize(N);
	ll i;
	for (i = 0; i < q.size(); i++) adj[p[i]].push_back(q[i]), adj[q[i]].push_back(p[i]);
	dfs();
	for (i = 0; i < N; i++) vis[i] = 0;
	ll s[3] = { a, b, c };
	ll pp[3] = { 0, 0, 0 };
	pp[(s[0] > s[1] ? 0 : 1)]++;
	pp[(s[1] > s[2] ? 1 : 2)]++;
	pp[(s[0] > s[2] ? 0 : 2)]++;
	ll m = s[pp[0]];
	ll asdf[3];
	asdf[pp[0]] = 0;
	asdf[pp[1]] = 1;
	asdf[pp[2]] = 2;
	pp[0] = asdf[0];
	pp[1] = asdf[1];
	pp[2] = asdf[2];
	for (i = 1; i < N; i++) {
		tree[i].push_back(prt[i]);
		tree[prt[i]].push_back(i);
	}
	c = 0;
	while (1) {
		ll ccc = 1;
		for (auto v : tree[c]) {
			if (v == prt[c]) continue;
			if (num[v] >= m) {
				ccc = 0, c = v;
				break;
			}
		}
		if (ccc) break;
	}
	ll nc = num[c];
	vector<ll> sav;
	chk(0, -1, 1);
	chk(c, prt[c], 0);
	for (auto v : tree[c]) {
		if (v == prt[c]) continue;
		if (memo[v] >= ord[c]) continue;
		if (nc - num[v] < m) break;
		if (N - nc >= s[pp[1]]) break;
		nc -= num[v];
		sav.push_back(v);
	}
	if (!(nc >= s[pp[0]] && (N - nc) >= s[pp[1]])) {
		sav.clear();
		nc = num[c];
		if (nc < s[pp[1]]) return res;
		for (auto v : tree[c]) {
			if (v == prt[c]) continue;
			if (memo[v] >= ord[c]) continue;
			if (nc - num[v] < s[pp[1]]) break;
			if (N - nc >= s[pp[0]]) break;
			nc -= num[v];
			sav.push_back(v);
		}
		if (!(nc >= s[pp[1]] && (N - nc) >= s[pp[0]])) return res;
		for (auto v : sav) chk(v, c, 1);
		cnt = 0;
		dfs2(0, -1, 1);
		for (i = 0; i < N; i++) vis[i] = 0;
		cnt = 0;
		dfs2(c, prt[c], 0);
		for (i = 0; i < N; i++) res[i] = pp[2] + 1;
		for (i = 0; i < N; i++) {
			if (!arr[i] && split[0][i] <= s[pp[1]]) {
				res[i] = pp[1] + 1;
			}
		}
		for (i = 0; i < N; i++) {
			if (arr[i] && split[1][i] <= s[pp[0]]) {
				res[i] = pp[0] + 1;
			}
		}
		vector<ll> v(4);
		for (i = 0; i < N; i++) {
			v[res[i]]++;
		}
		//assert(s[p[0]] == v[1] && s[p[1]] == v[2]);
		return res;
	}
	for (auto v : sav) chk(v, c, 1);
	cnt = 0;
	dfs2(0, -1, 1);
	for (i = 0; i < N; i++) vis[i] = 0;
	cnt = 0;
	dfs2(c, prt[c], 0);
	ll cnt1 = 0;
	for (i = 0; i < N; i++) cnt1 += arr[i];
	for (i = 0; i < N; i++) res[i] = pp[2] + 1;
	for (i = 0; i < N; i++) {
		if (!arr[i] && split[0][i] <= s[pp[0]]) {
			res[i] = pp[0] + 1;
		}
	}
	for (i = 0; i < N; i++) {
		if (arr[i] && split[1][i] <= s[pp[1]]) {
			res[i] = pp[1] + 1;
		}
	}
	vector<ll> v(4);
	for (i = 0; i < N; i++) {
		v[res[i]]++;
	}
	assert(s[0] == v[1] && s[1] == v[2]);
	return res;
}

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:55:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (i = 0; i < q.size(); i++) adj[p[i]].push_back(q[i]), adj[q[i]].push_back(p[i]);
      |              ~~^~~~~~~~~~

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