Submission #651312

#	Time	Username	Problem	Language	Result	Execution time	Memory
651312		ymm	Split the Attractions (IOI19_split)	C++17	40 / 100	1831 ms	23308 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
vector<int> A[N], At[N];
mt19937_64 rd(time(0));
bool vis[N];
int a, b, c;
int tag[3] = {1, 2, 3};
int n;

void sort_abc()
{
	if (a > b) {
		swap(a, b);
		swap(tag[0], tag[1]);
	}
	if (b > c) {
		swap(b, c);
		swap(tag[1], tag[2]);
	}
	if (a > b) {
		swap(a, b);
		swap(tag[0], tag[1]);
	}
}

void dfs2(int v, int p, vector<int> &vec)
{
	vec.push_back(v);
	for (int u : At[v])
		if (u != p)
			dfs2(u, v, vec);
}

vector<int> make_ans(vector<int> A, vector<int> B)
{
	vector<int> ans(n, tag[2]);
	for (int v : A)
		ans[v] = tag[0];
	for (int v : B)
		ans[v] = tag[1];
	return ans;
}

int sz[N];

void dfs0(int v)
{
	sz[v] = 1;
	vis[v] = 1;
	for (int u : A[v]) {
		if (!vis[u]) {
			At[v].push_back(u);
			At[u].push_back(v);
			dfs0(u);
			sz[v] += sz[u];
		}
	}
}

pii dfs1(int v, int p)
{
	for (int u : At[v])
		if (u != p && sz[u] >= a)
			return dfs1(u, v);
	if (n-sz[v] >= a)
		return {v, p};
	return {-1, -1};
}

vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
	n = _n; a = _a; b = _b; c = _c;
	sort_abc();
	Loop (i,0,p.size()) {
		A[p[i]].push_back(q[i]);
		A[q[i]].push_back(p[i]);
	}
	while (clock() < 1.8 * CLOCKS_PER_SEC) {
		Loop (i,0,n) {
			shuffle(A[i].begin(), A[i].end(), rd);
			At[i].clear();
		}
		memset(vis, 0, sizeof(vis));
		int rt = rd()%n;
		dfs0(rt);
		auto [x, y] = dfs1(rt, -1);
		if (x == -1)
			continue;
		vector<int> A, B;
		dfs2(x, y, A);
		dfs2(y, x, B);
		if (A.size() > B.size())
			A.swap(B);
		assert(A.size() >= a);
		assert(B.size() >= b);
		A.resize(a);
		B.resize(b);
		return make_ans(A, B);
	}
	return vector<int>(n, 0);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from split.cpp:2:
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:101:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |   assert(A.size() >= a);
      |          ~~~~~~~~~^~~~
split.cpp:102:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |   assert(B.size() >= b);
      |          ~~~~~~~~~^~~~

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