Submission #830253

#	Time	Username	Problem	Language	Result	Execution time	Memory
830253		GusterGoose27	Split the Attractions (IOI19_split)	C++17	18 / 100	2073 ms	17996 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> 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) {
	sz[cur] = 1;
	vis[cur] = 1;
	int ans = -1;
	for (int nxt: edges[cur]) {
		if (vis[nxt]) continue;
		ans = max(dfs(nxt, a, b), 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]) {
	vis[cur] = 1;
	if (cur == spec) val ^= 1;
	if (a[val]) {
		res[cur] = val;
		a[val]--;
	}
	for (int nxt: edges[cur]) {
		if (vis[nxt]) continue;
		assign(nxt, spec, val, a);
	}
}

bool test(int a, int b, mt19937 &gen) {
	int s = gen()%n;
	memset(vis, 0, sizeof(bool)*n);
	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);
		if (test(a, b, gen)) {
			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:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  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