Submission #821831

#	Time	Username	Problem	Language	Result	Execution time	Memory
821831		prvocislo	Split the Attractions (IOI19_split)	C++17	100 / 100	193 ms	20412 KiB

split

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "split.h"
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 1e5 + 5;
int n;
vector<int> siz; // velkosti podstromov
vector<vector<int> > g; // ten strom
void dfs_siz(int u)
{
	siz[u] = 1;
	for (int v : g[u]) if (!siz[v]) dfs_siz(v), siz[u] += siz[v];
}
int centroid()
{
	dfs_siz(0);
	for (int i = 0; i < n; i++)
	{
		if ((n - siz[i]) > n / 2) continue;
		bool bad = false;
		for (int j : g[i]) if (siz[j] < siz[i] && siz[j] > n / 2) bad = true;
		if (!bad) return i;
	}
	//cout << "WA\n";
}
vector<int> pr, s; // unionfind stuff
void reset() { for (int i = 0; i < n; i++) pr[i] = i, s[i] = 1; }
int root(int a) { return pr[a] == a ? a : pr[a] = root(pr[a]); }
bool merge(int a, int b)
{
	a = root(a), b = root(b);
	if (a == b) return false;
	pr[a] = b, s[b] += s[a];
	return true;
}
vector<int> ans;
void dfs_color(int u, int cl1, int cl2, int &cnt1, int &cnt2)
{
	if (cnt1) ans[u] = cl1, cnt1--;
	else ans[u] = cl2, cnt2--;
	for (int v : g[u]) if (!ans[v]) dfs_color(v, cl1, cl2, cnt1, cnt2);
}
void color(vector<int> cm, int cl1, int cl2, int &cnt1, int &cnt2, const vector<int> &p, const vector<int> &q)
{
	set<int> s(cm.begin(), cm.end());
	g.assign(n, {});
	for (int i = 0; i < p.size(); i++) if (s.count(p[i]) && s.count(q[i])) g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]);
	dfs_color(cm[0], cl1, cl2, cnt1, cnt2);
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
	vector<pair<int, int> > col = { {a, 1}, {b,2}, {c,3} };
	sort(col.begin(), col.end());
	int m = col[0].first;
	n = N, ans.assign(n, 0), siz.assign(n, 0), g.assign(n, {}), pr.assign(n, -1), s.assign(n, -1);
	reset();
	vector<int> strom, other;
	for (int i = 0; i < p.size(); i++)
	{
		if (merge(p[i], q[i])) g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]), strom.push_back(i);
		else other.push_back(i);
	}
	if (strom.size() != n - 1) return ans;
	int vr = centroid();
	reset();
	for (int i : strom) if (p[i] != vr && q[i] != vr) merge(p[i], q[i]);
	for (int i : other) if (p[i] != vr && q[i] != vr)
	{
		int a = root(p[i]), b = root(q[i]);
		if (s[a] < m && s[b] < m) merge(a, b);
	}
	int big = -1;
	for (int i = 0; i < n; i++) if (vr != i && pr[i] == i && s[i] >= m) big = i;
	if (big == -1) 
		return ans;
	vector<vector<int> > v(2);
	for (int i = 0; i < n; i++) v[root(i) == big].push_back(i);
	if (v[0].size() > v[1].size()) swap(v[0], v[1]);
	for (int i = 0; i < 2; i++) color(v[i], col[i].second, col[2].second, col[i].first, col[2].first, p, q);
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'void color(std::vector<int>, int, int, int&, int&, const std::vector<int>&, const std::vector<int>&)':
split.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (int i = 0; i < p.size(); i++) if (s.count(p[i]) && s.count(q[i])) g[p[i]].push_back(q[i]), g[q[i]].push_back(p[i]);
      |                  ~~^~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~
split.cpp:78:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   78 |  if (strom.size() != n - 1) return ans;
      |      ~~~~~~~~~~~~~^~~~~~~~
split.cpp: In function 'int centroid()':
split.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
   40 | }
      | ^

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