Submission #830257

#	Time	Username	Problem	Language	Result	Execution time	Memory
830257		GusterGoose27	Split the Attractions (IOI19_split)	C++17	18 / 100	2080 ms	23032 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];

vector<int> res;
bool vis[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)]);
}

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);
	}
}

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 1: bfs
	memset(vis, 0, sizeof(bool)*n);
	queue<int> q;
	q.push(s);
	vis[s] = 1;
	while (!q.empty()) {
		int t = q.front();
		q.pop();
		for (int nxt: edges[t]) {
			if (vis[nxt]) continue;
			tree[t].push_back(nxt);
			vis[nxt] = 1;
			q.push(nxt);
		}
	}
	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]);
	}
	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:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  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