Submission #1291750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291750		goulthen	Split the Attractions (IOI19_split)	C++20	0 / 100	2 ms	340 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];
bool vis[MAXN], mk[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(1);

	vector<int> A,B,C;

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

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

	rep(i,0,n-1) if(!mk[i]) B.pb(i);
	vector<int> res;
	for (int &x : A)res.pb(x);
	for (int &x : B)res.pb(x);
	for (int &x : C)res.pb(x);
	return res;
}

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