제출 #826957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
826957		vjudge1	Split the Attractions (IOI19_split)	C++17	18 / 100	61 ms	14612 KiB

split

#include <bits/stdc++.h>
#define ll long long
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

using namespace std;
#define pii pair <int, int>

const int maxn=2e5+10;

int n, m, a, b, c, col[maxn], ok, used[maxn];
vector <int> edge[maxn];

void dfs(int v)
{
	used[v] = 1;
	if(b)
	{
		col[v] = 2;
		b--;
	}
	else
	if(a)
	{
		col[v] = 1;
		a--;
	}
	for(auto to : edge[v])
	{
		if(used[to]) continue;
		dfs(to);
	}
}

vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q)
{
	n = N;
	m = q.size();
	forn(1, i, n) edge[i].clear();
	ok =  0;
	FOR(0, i, m)
	{
		q[i]++;
		p[i]++;
		edge[q[i]].pb(p[i]);
		edge[p[i]].pb(q[i]);
	}
	vector <pii> sor;
	sor.pb({A, 1});
	sor.pb({B, 2});
	sor.pb({C, 3});
	sort(all(sor));
	a = sor[0].f;
	b = sor[1].f;
	c = sor[2].f;

	dfs(1);
	forn(1, i, n)
	{
		if(col[i]) continue;
		if(a)
		{
			a--;
			col[i] = 1;
		}
		else
		if(c)
		{
			c--;
			col[i] = 3;
		}
	}
	vector <int> res(n, 0);
	forn(1, i, n)
	{
		if(col[i] == 0) col[i] = 3;
		res[i-1] = sor[col[i]-1].s;
	}
	return res;
}

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