oj.uz

Submission #144750

# Submission time Handle Problem Language Result Execution time Memory
144750 2019-08-17T15:51:16 Z abeker Split the Attractions (IOI19_split) C++17
33 / 100
 402 ms 71880 KB 
#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) {
		//printf("adding to block cut tree %d %d\n", x, 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] = 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);
		sgn[0] = 0;
		for (auto it : preorder) {
			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 = 0; 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) 
					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;

void output(const vector <int> &v) {
	for (auto it : v)
		printf("%d ", it);
	puts("");
}

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();
	
	//printf("centroid %d\n", node);
	//printf("sajz %d\n", T.adj[node].size());
	
	bool single = G.memo[node].size() == 1;
	for (auto it : T.adj[node]) {
		//printf("neighbour size %d %d\n", it.first, it.second);
		vector <int> branch;
		T.go(it.first, node, branch);
		//output(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());
		//output(tmp);
		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]);
	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);
	}
	
	return {};
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:236: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:262:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(tmp.size() == it.second);
          ~~~~~~~~~~~^~~~~~~
split.cpp:278:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (lft.size() >= parts[0].first)
       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Incorrect 2 ms 380 KB WA in grader: Invalid length of the result.
7 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 298 ms 53388 KB ok, correct split
5 Correct 332 ms 64416 KB ok, correct split
6 Correct 314 ms 71880 KB ok, correct split
7 Correct 360 ms 63860 KB ok, correct split
8 Correct 317 ms 47528 KB ok, correct split
9 Correct 267 ms 33704 KB ok, correct split
10 Correct 226 ms 61672 KB ok, correct split
11 Correct 232 ms 61668 KB ok, correct split
12 Correct 226 ms 61668 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB ok, correct split
2 Correct 359 ms 61576 KB ok, correct split
3 Correct 116 ms 26668 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 370 ms 66384 KB ok, correct split
6 Correct 402 ms 66060 KB ok, correct split
7 Correct 392 ms 66724 KB ok, correct split
8 Correct 391 ms 67868 KB ok, correct split
9 Correct 389 ms 65832 KB ok, correct split
10 Correct 67 ms 13780 KB ok, no valid answer
11 Correct 111 ms 21420 KB ok, no valid answer
12 Correct 189 ms 38184 KB ok, no valid answer
13 Correct 236 ms 42408 KB ok, no valid answer
14 Correct 145 ms 36696 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 9 ms 256 KB ok, no valid answer
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Incorrect 2 ms 376 KB WA in grader: Invalid length of the result.
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 376 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Incorrect 2 ms 380 KB WA in grader: Invalid length of the result.
7 Halted 0 ms 0 KB -