Submission #247549

#	Time	Username	Problem	Language	Result	Execution time	Memory
247549		nvmdava	Split the Attractions (IOI19_split)	C++17	100 / 100	179 ms	18952 KiB

split

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

#define ff first
#define ss second

const int N = 100005;

int n;
vector<pair<int, int> > sad;
vector<int> res;

int dsu[N];
int find(int v){
	return v == dsu[v]? v : dsu[v] = find(dsu[v]);
}

vector<pair<int, int> > supp;
vector<int> adj1[N];

int sz[N];

int cen(int v, int p){
	sz[v] = 1;
	int w = -1;
	for(auto& x : adj1[v]){
		if(x == p) continue;
		w = max(w, cen(x, v));
		sz[v] += sz[x];
	}
	if(w != -1) return w;
	if(n - sz[v] <= n / 2) return v;
	return -1;
}

void mina(int v, int p, int c){
	if(sad[c].ff == 0) return;
	--sad[c].ff;
	res[v] = sad[c].ss;
	for(auto& x : adj1[v]){
		if(x == p) continue;
		mina(x, v, c);
	}
}

int col[N];
void pnt(int v, int p, int c){
	col[v] = c;
	++sz[c];
	for(auto& x : adj1[v]){
		if(x == p)
			continue;
		pnt(x, v, c);
	}
}

vector<int> adj2[N];
bool vis[N];

int ss;

bool dfs(int v, int r){
	vis[v] = 1;
	ss += sz[v];
	dsu[v] = r;
	if(ss >= sad[0].ff) return 1;
	for(auto& x : adj2[v])
		if(dsu[x] != r)
			if(dfs(x, r)) return 1;
	return 0;

}

void minari(int v, int c){
	if(sad[c].ff == 0) return;
	res[v] = sad[c].ss;
	--sad[c].ff;
	for(auto& x : adj1[v])
		if(col[x] == col[v] && !res[x])
			minari(x, c);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	::n = n;
	res.resize(n);
	for(int i = 0; i < n; ++i)
		dsu[i] = i;
	
	sad.push_back({a, 1});
	sad.push_back({b, 2});
	sad.push_back({c, 3});
	sort(sad.begin(), sad.end());

	for(int i = 0; i < p.size(); ++i){
		if(find(p[i]) == find(q[i])) supp.push_back({p[i], q[i]});
		else {
			dsu[find(p[i])] = find(q[i]);
			adj1[p[i]].push_back(q[i]);
			adj1[q[i]].push_back(p[i]);
		}
	}

	int r = cen(0, -1);
	cen(r, -1);

	for(int i = 0; i < adj1[r].size(); ++i){
		if(sz[adj1[r][i]] >= sad[0].ff){
			mina(adj1[r][i], r, 0);
			mina(r, adj1[r][i], 1);
			for(int j = 0; j < n; ++j)
				if(!res[j])
					res[j] = sad[2].ss;
			return res;
		}
	}


	for(int i = 0; i < n; ++i)
		sz[i] = 0;

	for(int i = 0; i < adj1[r].size(); ++i)
		pnt(adj1[r][i], r, i + 1);

	for(auto& x : supp){
		if(col[x.ff] == col[x.ss] || x.ff == r || x.ss == r) continue;
		adj2[col[x.ff]].push_back(col[x.ss]);
		adj2[col[x.ss]].push_back(col[x.ff]);
	}

	for(int i = 0; i < n; ++i)
		dsu[i] = i;

	for(int i = 0; i <= n; ++i){
		ss = 0;
		if(!vis[i] && dfs(i, i)){
			for(int j = 0; j < n; ++j){
				col[j] = dsu[col[j]];
				if(col[j] != i) col[j] = 0;
			}

			for(auto& x : supp){
				adj1[x.ff].push_back(x.ss);
				adj1[x.ss].push_back(x.ff);
			}

			minari(adj1[r][i - 1], 0);
			minari(r, 1);
			for(int j = 0; j < n; ++j)
				if(!res[j])
					res[j] = sad[2].ss;


			return res;
		}
	}


	return res;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < p.size(); ++i){
                 ~~^~~~~~~~~~
split.cpp:107:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj1[r].size(); ++i){
                 ~~^~~~~~~~~~~~~~~~
split.cpp:122:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj1[r].size(); ++i)
                 ~~^~~~~~~~~~~~~~~~

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