제출 #1046380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1046380		abczz	Split the Attractions (IOI19_split)	C++17	100 / 100	101 ms	30156 KiB

split

#include "split.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

ll n, f, z, sz[100000], D[100000], P[100000], back[100000];
vector <ll> adj[100000], E[100000], opt;
bool visited[100000], X[100000];
vector <int> F;
array<ll, 2> A[3];

void dfs_tree(ll u) {
	visited[u] = 1;
	for (auto v : adj[u]) {
		if (!visited[v]) {
			P[v] = u;
			E[u].push_back(v);
			D[v] = D[u] + 1;
			dfs_tree(v);
		}
		else back[u] = min(back[u], D[v]);
	}
}

void dfs_sz(ll u) {
	sz[u] = 1;
	for (auto v : E[u]) {
		dfs_sz(v);
		back[u] = min(back[u], back[v]);
		sz[u] += sz[v];
	}
	if (A[0][0] <= sz[u] && sz[u] <= n-A[0][0]) f = u;
	ll tot = sz[u];
	vector <ll> tmp;
	for (auto v : E[u]) {
		if (back[v] < D[u]) {
			tmp.push_back(v);
			tot -= sz[v];
			if (z == -1 && A[0][0] <= tot && tot <= n-A[0][0]) {
				z = u;
				opt = tmp;
				break;
			}
		}
	}
}

void paint(ll u, ll id) {
	if (A[id][0]) {
		--A[id][0];
		F[u] = A[id][1];
	}
	for (auto v : E[u]) {
		paint(v, id);
	}
}

void solve(ll u, ll id) {
	if (A[id][0] && F[u] == A[2][1]) {
		--A[id][0];
		F[u] = A[id][1];
	}
	for (auto v : adj[u]) {
		if (!A[id][0]) return;
		if (F[v] == A[2][1]) solve(v, id);
	}
}

vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
	n = _n, f = z = -1;
	A[0] = {a, 1}, A[1] = {b, 2}, A[2] = {c, 3};
	sort(A, A+3);
	for (int i=0; i<n; ++i) {
		X[i] = 0;
		back[i] = 1e18;
		adj[i].clear();
		E[i].clear();
		F.push_back(A[2][1]);
		visited[i] = 0;
	}
	for (int i=0; i<p.size(); ++i) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	dfs_tree(0);
	dfs_sz(0);
	if (f != -1) {
		if (A[0][0] <= sz[f] && sz[f] <= n-A[1][0]) {
			paint(f, 0);
			solve(P[f], 1);
		}
		else {
			paint(f, 1);
			solve(P[f], 0);
		}
	}
	else if (z != -1) {
		ll tot = sz[z];
		for (auto u : opt) tot -= sz[u], X[u] = 1;
		if (A[0][0] <= tot && tot <= n-A[1][0]) {
			F[z] = A[0][1];
			--A[0][0];
			for (auto v : E[z]) {
				if (!X[v]) paint(v, 0);
			}
			for (auto v : E[z]) {
				if (X[v]) solve(v, 1);
			}
		}
		else {
			F[z] = A[1][1];
			--A[1][0];
			for (auto v : E[z]) {
				if (!X[v]) paint(v, 1);
			}
			for (auto v : E[z]) {
				if (X[v]) solve(v, 0);
			}
		}
	}
	else {
		for (auto &u : F) u = 0;
	}
	return F;
}

/*
x > n-a
y < a

n-a-ka > a
*/

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

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

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