Submission #1047675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047675		efedmrlr	Split the Attractions (IOI19_split)	C++17	22 / 100	473 ms	1048576 KiB

split

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include "split.h"
using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()



const double EPS = 0.00001;
const int INF = 1e9+500;

const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
using namespace std;


vector<vector<int> > adj;
vector<int> pr, sub;
vector<array<int, 2> > ord(3);
vector<int> ans;
int m, N;
vector<int> spl(2, -1);
void dfs(int node, int par) {
	pr[node] = par;
	sub[node] = 1;
	for(auto c : adj[node]) {
		if(c == pr[node]) continue;
		dfs(c, node);
		sub[node] += sub[c];
	}
	if(spl[0] != -1) return;
	vector<int> szs = {N - sub[node], sub[node]};
	bool swa = 0;

	if(szs[0] > szs[1]) {
		swa = 1;
		swap(szs[0], szs[1]);
	}
	// cout << "node: " << node << " p:" << pr[node] << " sub:" << sub[node] << " sz0:" << szs[0] << " sz1: " << szs[1] << "\n"; 
	if(szs[0] >= ord[0][0] && szs[1] >= ord[1][0]) {
		spl[0] = 0; spl[1] = node;
		if(swa) swap(spl[0], spl[1]);
	}
}
int cnt = 0;
void dfs2(int node, int forb, int num) {
	if(node == forb || cnt == ord[num][0]) return;
	cnt++;
	ans[node] = ord[num][1];
	for(auto c : adj[node]) {
		if(c == pr[node]) continue;
		dfs2(c, forb, num);
	}

}

array<int, 2> cycle_dfs(int node, int start, int cur, int par) {
	if(cnt == ord[cur][0] || node == start) {
		return {node, par};
	}
	ans[node] = ord[cur][1];
	cnt++; 
	for(auto c : adj[node]) {
		if(c == par) continue;
		return cycle_dfs(c, start, cur, node);
	}
}

void solve_cycle() {
	cnt = 1;
	ans[0] = ord[0][1];
	auto last = cycle_dfs(adj[0][0], 0, 0, 0);
	cnt = 0;
	last = cycle_dfs(last[0], 0, 1, last[1]);
	cnt = 0;
	last = cycle_dfs(last[0], 0, 2, last[1]);
	
}


vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	adj.assign(n, vector<int>());
	ans.assign(n, 0);
	sub.assign(n, 0);
	spl.assign(2, -1);
	ord.resize(3);
	ord[0] = {a, 1};
	ord[1] = {b, 2};
	ord[2] = {c, 3};
	sort(all(ord));
	N = n;
	pr.assign(n, 0);
	m = (int)p.size();
	
	int mxx = 0;
	for(int i = 0; i < m; i++) {
		adj[p[i]].pb(q[i]);
		adj[q[i]].pb(p[i]);
	}
	REP(i, n) {
		mxx = max(mxx, (int)adj[i].size());
	}
	if(mxx == 2) {
		solve_cycle();
		return ans;
	}
	dfs(0, 0);
	if(spl[0] == -1) {
		return ans;
	}
	cnt = 0;
	dfs2(spl[0], spl[1], 0);
	cnt = 0;
	dfs2(spl[1], spl[0], 1);
	REP(i, n) {
		if(ans[i] == 0) ans[i] = ord[2][1];
	}
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::array<int, 2> cycle_dfs(int, int, int, int)':
split.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
   77 | }
      | ^

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