Submission #256069

#	Time	Username	Problem	Language	Result	Execution time	Memory
256069		b00n0rp	Split the Attractions (IOI19_split)	C++17	7 / 100	133 ms	25852 KiB

split

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

#define ll long long
#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define pii pair<int,int>
#define F first
#define S second
using namespace std;

const int MX = 200005;

vi g[MX],adj[MX];
int par[MX];

bitset<MX> vis;

void dfs(int u,int p){
	// cout << u << " " << p << endl;
	par[u] = p;
	vis[u] = 1;
	for(auto v:g[u]){
		if(vis[v]) continue;
		adj[u].pb(v);
		par[v] = u;
		dfs(v,u);
	}
}

vi find_split(int n, int a, int b, int c, vi p, vi q) {
	REP(i,(int)p.size()){
		g[p[i]].pb(q[i]);
		g[q[i]].pb(p[i]);
	}
	int mxd = 0;
	int root = 0;
	REP(i,n){
		mxd = max(mxd,(int)g[i].size());
		if(g[i].size() == 1) root = i;
	}
	dfs(root,root);
	vi ans(n);
	if(mxd == 2){
		int cur = root,cnt = 0;
		while(1){
			if(cnt < a) ans[cur] = 1;
			else if(cnt < a+b) ans[cur] = 2;
			else ans[cur] = 3;
			cnt++;
			if(adj[cur].size()) cur = adj[cur][0];
			else break;
		}
	}
	return ans;
}

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