Submission #144769

#	Time	Username	Problem	Language	Result	Execution time	Memory
144769		abeker	Split the Attractions (IOI19_split)	C++17	100 / 100	420 ms	72868 KiB

split

#include <bits/stdc++.h>
using namespace std;

typedef pair <int, int> pii;

struct tree {
	int n;
	vector <int> weight, dad;
	vector <vector <pii>> adj;
	
	tree() {
		n = 0;
	}
	
	int add_node() {
		weight.push_back(0);
		dad.push_back(-1);
		adj.push_back({});
		return n++;
	}
	
	void add_edge(int x, int y) {
		adj[x].push_back({y, 0});
		adj[y].push_back({x, 0});
	}
	
	void set_weight(int x, int w) {
		weight[x] = w;
	}
	
	void calc(int x, int p) {
		dad[x] = p;
		for (auto &it : adj[x]) 
			if (it.first != p) {
				calc(it.first, x);
				weight[x] += weight[it.first];
				it.second = weight[it.first];
			}
	}
	
	int centroid() {
		for (int i = 0; i < n; i++) {
			int mx = 0;
			for (auto &it : adj[i]) {
				if (it.first == dad[i])
					it.second = weight[0] - weight[i];
				mx = max(mx, it.second);
			}
			if (mx <= weight[0] / 2)
				return i;
		}
		assert(false);
	}
	
	void go(int x, int p, vector <int> &v) {
		v.push_back(x);
		for (auto it : adj[x])
			if (it.first != p)
				go(it.first, x, v);
	}
};

struct graph {
	int n, timer;
	vector <vector <int>> adj;
	vector <int> disc, low;
	vector <int> dad, link;
	vector <vector <int>> comps;
	vector <vector <int>> memo, group;
	vector <int> preorder;
	stack <int> stk;
	vector <bool> art;
	vector <int> idx;
	
	graph(int _n) {
		n = _n;
		timer = 0;
		disc.resize(n);
		low.resize(n);
		dad.resize(n);
		link.resize(n);
		art.resize(n);
		idx.resize(n);
		adj.resize(n);
		memo.resize(2 * n);
		group.resize(n);
		for (int i = 0; i < n; i++)
			group[i] = {i};
	}
	
	graph(){}
	
	void add_edge(int x, int y) {
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	
	void dfs(int x, int p) {
		preorder.push_back(x);
		disc[x] = low[x] = ++timer;
		link[x] = x;
		dad[x] = p;
		stk.push(x);
		for (auto it : adj[x])
			if (!disc[it]) {
				dfs(it, x);
				if (low[it] < low[x]) {
					low[x] = low[it];
					link[x] = link[it];
				}
				if (low[it] >= disc[x]) {
					art[x] = disc[x] > 1 || disc[it] > 2;
					comps.push_back({x});
					for (; comps.back().back() != it; stk.pop())
						comps.back().push_back(stk.top());
				}
			}
			else if (it != p && disc[it] < low[x]) {
				low[x] = disc[it];
				link[x] = it;
			}
	}
	
	tree block_cut() {
		tree res;
		for (int i = 0; i < n; i++)
			if (art[i]) {
				idx[i] = res.add_node();
				res.set_weight(idx[i], 1);
				memo[idx[i]] = {i};
			}
		
		for (auto comp : comps) {
			int node = res.add_node();
			int sz = comp.size();
			memo[node] = comp;
			for (auto it : comp)
				if (art[it]) {
					res.add_edge(node, idx[it]);
					sz--;
				}
			res.set_weight(node, sz);
		}
		
		return res;
	}
	
	vector <int> st_numbering() {
		vector <int> prv(n, -1), nxt(n, -1), sgn(n, -1);
		int s = preorder[0];
		int t = preorder[1];
		sgn[s] = 0;
		nxt[s] = t;
		prv[t] = s;
		for (auto it : preorder) {
			if (disc[it] <= 2)
				continue;
			if (sgn[link[it]]) {
				sgn[dad[it]] = 0;
				if (nxt[dad[it]] != -1)
					prv[nxt[dad[it]]] = it;
				nxt[it] = nxt[dad[it]];
				prv[it] = dad[it];
				nxt[dad[it]] = it;
			}
			else {
				sgn[dad[it]] = 1;
				if (prv[dad[it]] != -1)
					nxt[prv[dad[it]]] = it;
				prv[it] = prv[dad[it]];
				nxt[it] = dad[it];
				prv[dad[it]] = it;
			}
		}
		
		vector <int> res;
		for (int x = s; x != -1; x = nxt[x])
			res.push_back(x);
		
		return res;
	}
	
	graph induced(const vector <int> &subset) {
		vector <int> label(n, -1);
		int sz = subset.size();
		for (int i = 0; i < sz; i++)
			label[subset[i]] = i;
		
		graph res(sz);
		for (int i = 0; i < sz; i++)
			for (auto it : adj[subset[i]])
				if (label[it] != -1 && i < label[it]) 
					res.add_edge(i, label[it]);
		
		return res;
	}
	
	vector <int> clip(int num) {
		dfs(0, -1);
		preorder.resize(num);
		return preorder;
	}
	
	vector <int> construct(const vector <int> &subset, const vector <pii> &p) {
		vector <bool> in(n, false);
		for (auto it : subset)
			in[it] = true;
		
		vector <int> rest;
		for (int i = 0; i < n; i++)
			if (!in[i])
				rest.push_back(i);
		
		vector <int> A = induced(subset).clip(p[0].first);
		vector <int> B = induced(rest).clip(p[1].first);
		
		vector <int> res(n, p[2].second);
		for (auto it : A)	
			res[subset[it]] = p[0].second;
		for (auto it : B)
			res[rest[it]] = p[1].second;
		
		return res;
	}
};

graph G, H;
tree T;

vector <int> find_split(int N, int a, int b, int c, vector <int> u, vector <int> v) {
	vector <pii> parts = {{a, 1}, {b, 2}, {c, 3}};
	sort(parts.begin(), parts.end());
	
	G = graph(N);
	for (int i = 0; i < u.size(); i++)
		G.add_edge(u[i], v[i]);
	
	G.dfs(0, -1);
	
	T = G.block_cut();
	T.calc(0, -1);
	int node = T.centroid();
	
	bool single = G.memo[node].size() == 1;
	for (auto it : T.adj[node]) {
		vector <int> branch;
		T.go(it.first, node, branch);
		vector <int> tmp;
		for (auto it1 : branch)
			for (auto it2 : G.memo[it1])
				if (!single || it2 != G.memo[node][0]) 
					tmp.push_back(it2);
		sort(tmp.begin(), tmp.end());
		tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
		assert(tmp.size() == it.second);
		G.group[G.memo[it.first][0]] = tmp;
		if (it.second >= parts[0].first)
			return G.construct(tmp, parts);
	}
	
	if (single)
		return vector <int> (N, 0);
	
	H = G.induced(G.memo[node]);
	H.dfs(0, -1);
	vector <int> order = H.st_numbering();
	vector <int> lft;
	for (auto it : order) {
		int tmp = G.memo[node][it];
		for (auto it1 : G.group[tmp])
			lft.push_back(it1);
		if (lft.size() >= parts[0].first)
			return G.construct(lft, parts);
	}
	
	assert(false);
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:235:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < u.size(); i++)
                  ~~^~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from split.cpp:1:
split.cpp:255:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(tmp.size() == it.second);
          ~~~~~~~~~~~^~~~~~~
split.cpp:272:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (lft.size() >= parts[0].first)
       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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