제출 #1150921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150921		gyg	Split the Attractions (IOI19_split)	C++20	18 / 100	54 ms	14692 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array 
#define vec vector
#define pii pair<int, int>
#define fir first 
#define sec second
const int N = 1e5 + 5;

int n, a, b, c;
arr<vec<int>, N> adj;

arr<bool, N> vs;
vec<int> ord;
void dfs(int u) {
	vs[u] = true, ord.push_back(u);
	for (int v : adj[u])
		if (!vs[v]) dfs(v);
}

arr<int, N> ans;
vec<sig> find_split(sig _n, sig _a, sig _b, sig _c, vec<sig> _u, vec<sig> _v) {
	n = _n, a = _a, b = _b, c = _c;
	for (int i = 0; i < _u.size(); i++) {
		int u = _u[i] + 1, v = _v[i] + 1;
		adj[u].push_back(v), adj[v].push_back(u);
	}

	vec<pii> srt = {{a, 1}, {b, 2}, {c, 3}};
	sort(srt.begin(), srt.end());
	a = srt[0].fir, b = srt[1].fir, c = srt[2].fir;

	int st = 1;
	for (int u = 1; u <= n; u++)
		if (adj[u].size() == 1) st = u;
	dfs(st);

	for (int i = 0; i < ord.size(); i++) {
		if (i < a) ans[ord[i]] = 1;
		else if (i < a + b) ans[ord[i]] = 2;
		else ans[ord[i]] = 3;
	}

	vec<sig> rsp;
	for (int u = 1; u <= n; u++) rsp.push_back(srt[ans[u] - 1].sec);
	return rsp;
}

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