Submission #1010308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010308		ttamx	Split the Attractions (IOI19_split)	C++17	40 / 100	51 ms	17240 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n;
vector<int> adj[N];
int disc[N],low[N],sz[N];
int timer=0;
bool vis[N];

void dfs(int u,int p=-1){
	disc[u]=low[u]=++timer;
	sz[u]=1;
	for(auto v:adj[u]){
		if(!disc[v]){
			dfs(v,u);
			low[u]=min(low[u],low[v]);
			sz[u]+=sz[v];
		}else if(v!=p){
			low[u]=min(low[u],disc[v]);
		}
	}
}

vector<int> find_split(int _n,int a,int b,int c,vector<int> p,vector<int> q){
	n=_n;
	for(int i=0;i<p.size();i++){
		int u=p[i],v=q[i];
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	dfs(0);
	pair<int,int> d[3]={{a,1},{b,2},{c,3}};
	sort(d,d+3);
	a=d[0].first,b=d[1].first;
	for(int u=1;u<n;u++){
		bool ok=sz[u]>=a;
		for(auto v:adj[u])if(disc[v]>disc[u])ok&=sz[v]<a;
		if(!ok)continue;
		vector<int> sub;
		int cur=sz[u];
		for(auto v:adj[u])if(disc[v]>disc[u]){
			if(low[v]<disc[u]&&cur-sz[v]>=a){
				cur-=sz[v];
			}else{
				sub.emplace_back(v);
			}
		}
		if(n-cur<a)continue;
		vector<int> ans(n,d[2].second);
		if(cur>n-cur)swap(d[0],d[1]);
		ans[u]=d[0].second;
		vis[u]=true;
		for(int i=0;i<d[0].first-1;i++){
			int x=sub[i];
			vis[x]=true;
			ans[x]=d[0].second;
			for(auto v:adj[x])if(disc[v]>disc[x])sub.emplace_back(v);
		}
		queue<int> q;
		q.emplace(0);
		vis[0]=true;
		for(int i=0;i<d[1].first;i++){
			int x=q.front();
			q.pop();
			ans[x]=d[1].second;
			for(auto v:adj[x])if(!vis[v]){
				vis[v]=true;
				q.emplace(v);
			}
		}
		return ans;
	}
	return vector<int>(n);
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~

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