Submission #830259

#	Time	Username	Problem	Language	Result	Execution time	Memory
830259		GusterGoose27	Split the Attractions (IOI19_split)	C++17	18 / 100	2083 ms	19012 KiB

split

#pragma GCC optimize("unroll-loops")

#include "split.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5+5;
int n, m;

// vector<int> edges[MAXN];
vector<int> tree[MAXN];

pii elist[2*MAXN];
vector<int> res;
// bool vis[MAXN];
int uf[MAXN];
int rnk[MAXN];
int sz[MAXN];

void perm(vector<int> &a, mt19937 &gen) {
	for (int i = 1; i < a.size(); i++) swap(a[i], a[gen()%(i+1)]);
}

void perm(pii a[], mt19937 &gen) {
	for (int i = 1; i < m; i++) swap(a[i], a[gen()%(i+1)]);
}

int dfs(int cur, int a, int b, int p = -1) {
	sz[cur] = 1;
	// vis[cur] = 1;
	int ans = -1;
	for (int nxt: tree[cur]) {
		if (nxt == p) continue;
		ans = max(dfs(nxt, a, b, cur), ans);
		sz[cur] += sz[nxt];
	}
	if (sz[cur] >= a && n-sz[cur] >= b) ans = 2*cur;
	else if (sz[cur] >= b && n-sz[cur] >= a) ans = 2*cur+1;
	return ans;
}

void assign(int cur, int spec, bool val, int a[2], int p = -1) {
	if (cur == spec) val ^= 1;
	if (a[val]) {
		res[cur] = val;
		a[val]--;
	}
	for (int nxt: tree[cur]) {
		if (nxt == p) continue;
		assign(nxt, spec, val, a, cur);
	}
}

int find(int i) {
	return uf[i] == -1 ? i : uf[i] = find(uf[i]);
}

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (rnk[a] < rnk[b]) swap(a, b);
	uf[b] = a;
	if (rnk[a] == rnk[b]) rnk[a]++;
}

bool test(int a, int b, mt19937 &gen, int s) {
	for (int i = 0; i < n; i++) {
		tree[i].clear();
		// perm(edges[i], gen);
	}
	// trial 2: kruskal
	memset(rnk, 0, sizeof(int)*n);
	fill(uf, uf+n, -1);
	perm(elist, gen);
	for (int i = 0; i < m; i++) {
		if (find(elist[i].first) != find(elist[i].second)) {
			merge(elist[i].first, elist[i].second);
			tree[elist[i].first].push_back(elist[i].second);
			tree[elist[i].second].push_back(elist[i].first);
		}
	}
	int ans = dfs(s, a, b);
	if (ans == -1) return 0;
	// memset(vis, 0, sizeof(bool)*n);
	res = vector<int>(n, 2);
	int cur[2]; cur[0] = a; cur[1] = b;
	assign(s, ans/2, (ans&1)^1, cur);
	return 1;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	n = N;
	m = p.size();
	vector<pii> change({{a, 1}, {b, 2}, {c, 3}});
	sort(change.begin(), change.end());
	a = change[0].first;
	b = change[1].first;
	for (int i = 0; i < m; i++) {
		// edges[p[i]].push_back(q[i]);
		// edges[q[i]].push_back(p[i]);
		elist[i] = pii(p[i], q[i]);
	}
	bool f = 0;
	mt19937 gen(0);
	for (int i = 0; i < 100000; i++) {
		// perm(edges[i%n], gen);
		// perm(edges[(i+n/2)%n], gen);
		if (test(a, b, gen, i%n)) {
			f = 1;
			break;
		}
	}
	if (f) for (int i = 0; i < n; i++) res[i] = change[res[i]].second;
	else res = vector<int>(n, 0);
	return res;
}

Compilation message (stderr)

split.cpp: In function 'void perm(std::vector<int>&, std::mt19937&)':
split.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i = 1; i < a.size(); i++) swap(a[i], a[gen()%(i+1)]);
      |                  ~~^~~~~~~~~~

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