Submission #1291766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291766		goulthen	Split the Attractions (IOI19_split)	C++20	11 / 100	66 ms	23852 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define pb push_back

using namespace std;
const int MAXN = 1e5+10;
vector<int> g[MAXN],t[MAXN];
int deg[MAXN],mk[MAXN];
bool vis[MAXN];

void dfs(int u) {
	if (vis[u]) return;
	vis[u] = 1;

	for (int &v : g[u]) if(!vis[v]) {
		t[u].pb(v);
		t[v].pb(u);
		deg[u]++;
		deg[v]++;
		dfs(v);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	rep(i,0,p.size()-1) {
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}

	dfs(0);

	int cnt = 0;
	rep(i,0,n-1) mk[i] = 2;
	//rep(i,0,n-1) cout << mk[i] << '\n';

	vector<int> ord;
	rep(i,0,n-1) if(deg[i] == 1) ord.pb(i);
	while (cnt != a+c) {
		int j = ord.back();ord.pop_back();
		if(cnt==0) mk[j]=1;
		else mk[j]=3;
		++cnt;

		for(int &v : t[j]) {
			if(mk[v]!=2) continue;
			if(--deg[v] == 1) ord.pb(v);
		}
	}

	vector<int> res;
	rep(i,0,n-1) res.pb(mk[i]);
	return res;
}

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