Submission #1237126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237126		AMnu	Split the Attractions (IOI19_split)	C++20	100 / 100	88 ms	18760 KiB

split

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

const int MAXN=1e5+5;

int N, M, cnt;
int sub[MAXN];
int low[MAXN];
int dis[MAXN];
pair<int,int> S[3];
vector<int> adj[MAXN];
vector<int> ans;

void dfs2(int now,int x) {
	if (ans[now]||!cnt) return;
	cnt--;
	ans[now]=x;
	for (int next : adj[now]) {
		if (dis[next]>=dis[now]) dfs2(next,x);
	}
}

int dfs(int now) {
	if (sub[now]||!ans.empty()) return 0;
	sub[now]=1;
	dis[now]=low[now]=++cnt;
	int maks=0;
	for (int next : adj[now]) {
		int save=dfs(next);
		maks=max(maks,save);
		sub[now]+=save;
		low[now]=min(low[now],dis[next]);
	}
	if (sub[now]>=S[0].first&&maks<S[0].first) {
		int size=N-sub[now];
		for (int next : adj[now]) {
			if (size>=S[0].first) break;
			if (dis[next]<dis[now]) continue;
			if (low[next]>=dis[now]) continue;
			size+=sub[next];
			dis[next]=0;
		}
		ans=vector<int>(N);
		if (size>=S[0].first) {
			if (size<S[1].first) {
				swap(S[0],S[1]);
			}
			cnt=S[0].first;
			dfs2(now,S[0].second);
			memset(dis,0,sizeof(dis));
			cnt=S[1].first;
			dfs2(0,S[1].second);
			for (int i=0;i<N;i++) if (!ans[i]) ans[i]=S[2].second;
		}
	}
	return sub[now];
}

vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q) {
	N=n;
	M=p.size();
	for (int i=0;i<M;i++) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	S[0]={a,1};
	S[1]={b,2};
	S[2]={c,3};
	sort(S,S+3);
	dfs(0);
	return ans;
}

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