Submission #650972

#	Time	Username	Problem	Language	Result	Execution time	Memory
650972		ymm	Split the Attractions (IOI19_split)	C++17	18 / 100	1820 ms	15636 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<pii> edges;
vector<int> A[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]);
	}
}

int par[N];
int sz[N];
int rt(int v){return par[v]==-1?v:rt(par[v]);}

bool unite(int v, int u)
{
	v = rt(v);
	u = rt(u);
	if (v == u || sz[v] >= b || sz[u] >= b)
		return 0;
	if (sz[v] < sz[u])
		swap(v, u);
	sz[v] += sz[u];
	par[u] = v;
	return sz[v] >= b;
}

void dfs(int v, vector<int> &vec)
{
	vis[v] = 1;
	vec.push_back(v);
	for (int u : A[v])
		if (!vis[u])
			dfs(u, 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;
}

pair<vector<int>,vector<int>> test(int v)
{
	Loop (i,0,n)
		vis[i] = rt(i) != v;
	vector<int> A, B;
	dfs(v, B);
	assert(B.size() >= b);
	B.resize(b);
	fill(vis, vis+n, 0);
	for (int v : B)
		vis[v] = 1;
	Loop (v,0,n) {
		if (vis[v])
			continue;
		A.clear();
		dfs(v, A);
		if (A.size() >= a) {
			A.resize(a);
			return {A, B};
		}
	}
	return {{}, {}};
}

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()) {
		edges.push_back({p[i], q[i]});
		A[p[i]].push_back(q[i]);
		A[q[i]].push_back(p[i]);
	}
	Loop (i,0,n)
		shuffle(A[i].begin(), A[i].end(), rd);
	if (a == 1) {
		vector<int> tmp;
		dfs(0, tmp);
		int v = tmp.back();
		tmp.resize(b);
		return make_ans({v}, tmp);
	}
	while (clock() < 1.8 * CLOCKS_PER_SEC) {
		shuffle(edges.begin(), edges.end(), rd);
		fill(par, par+n, -1);
		fill(sz, sz+n, 1);
		for (auto [v, u] : edges) {
			if (unite(v, u)) {
				auto [A, B] = test(rt(v));
				if (A.size())
					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::pair<std::vector<int>, std::vector<int> > test(int)':
split.cpp:77:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |  assert(B.size() >= b);
      |         ~~~~~~~~~^~~~
split.cpp:87:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |   if (A.size() >= a) {
      |       ~~~~~~~~~^~~~

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