oj.uz

Submission #144767

# Submission time Handle Problem Language Result Execution time Memory
144767 2019-08-17T16:19:18 Z abeker Split the Attractions (IOI19_split) C++17
100 / 100
 387 ms 72964 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] = 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;
			//printf("currently at %d %d\n", it, link[it]);
			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;

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());
	//printf("memo sajz %d\n", G.memo[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);
	
	//output(G.memo[node]);
	
	H = G.induced(G.memo[node]);
	H.dfs(0, -1);
	vector <int> order = H.st_numbering();
	//output(order);
	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:243: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:270:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(tmp.size() == it.second);
          ~~~~~~~~~~~^~~~~~~
split.cpp:290:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (lft.size() >= parts[0].first)
       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 256 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 256 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 376 KB ok, correct split
7 Correct 353 ms 67136 KB ok, correct split
8 Correct 383 ms 63976 KB ok, correct split
9 Correct 347 ms 63136 KB ok, correct split
10 Correct 295 ms 72964 KB ok, correct split
11 Correct 278 ms 66784 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 2 ms 376 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 260 ms 52116 KB ok, correct split
5 Correct 305 ms 64032 KB ok, correct split
6 Correct 286 ms 72876 KB ok, correct split
7 Correct 355 ms 63768 KB ok, correct split
8 Correct 288 ms 45372 KB ok, correct split
9 Correct 177 ms 33640 KB ok, correct split
10 Correct 237 ms 61240 KB ok, correct split
11 Correct 215 ms 61408 KB ok, correct split
12 Correct 190 ms 61284 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 318 ms 61084 KB ok, correct split
3 Correct 106 ms 26320 KB ok, correct split
4 Correct 3 ms 376 KB ok, correct split
5 Correct 343 ms 66524 KB ok, correct split
6 Correct 329 ms 66084 KB ok, correct split
7 Correct 373 ms 66916 KB ok, correct split
8 Correct 359 ms 67756 KB ok, correct split
9 Correct 366 ms 65740 KB ok, correct split
10 Correct 67 ms 13740 KB ok, no valid answer
11 Correct 132 ms 21420 KB ok, no valid answer
12 Correct 185 ms 38180 KB ok, no valid answer
13 Correct 244 ms 42380 KB ok, no valid answer
14 Correct 142 ms 36580 KB ok, no valid answer

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB ok, correct split
2 Correct 2 ms 376 KB ok, no valid answer
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 252 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 256 KB ok, correct split
7 Correct 2 ms 376 KB ok, correct split
8 Correct 2 ms 256 KB ok, correct split
9 Correct 6 ms 1144 KB ok, correct split
10 Correct 7 ms 1400 KB ok, correct split
11 Correct 2 ms 376 KB ok, correct split
12 Correct 7 ms 1528 KB ok, correct split
13 Correct 2 ms 376 KB ok, correct split
14 Correct 2 ms 256 KB ok, correct split
15 Correct 2 ms 376 KB ok, correct split
16 Correct 2 ms 376 KB ok, correct split
17 Correct 2 ms 376 KB ok, correct split
18 Correct 2 ms 376 KB ok, correct split
19 Correct 3 ms 632 KB ok, correct split
20 Correct 4 ms 860 KB ok, correct split
21 Correct 8 ms 1912 KB ok, correct split
22 Correct 8 ms 1912 KB ok, correct split
23 Correct 8 ms 2040 KB ok, correct split
24 Correct 8 ms 1912 KB ok, correct split
25 Correct 8 ms 2040 KB ok, correct split
26 Correct 7 ms 1784 KB ok, correct split
27 Correct 7 ms 1784 KB ok, correct split
28 Correct 7 ms 1784 KB ok, correct split
29 Correct 3 ms 504 KB ok, correct split
30 Correct 6 ms 1272 KB ok, correct split
31 Correct 3 ms 636 KB ok, correct split
32 Correct 3 ms 492 KB ok, correct split
33 Correct 3 ms 504 KB ok, correct split
34 Correct 8 ms 1912 KB ok, correct split
35 Correct 8 ms 1656 KB ok, correct split
36 Correct 8 ms 1784 KB ok, correct split
37 Correct 8 ms 1784 KB ok, correct split
38 Correct 8 ms 1784 KB ok, correct split
39 Correct 8 ms 1912 KB ok, correct split
40 Correct 8 ms 1784 KB ok, correct split
41 Correct 5 ms 1020 KB ok, correct split
42 Correct 5 ms 1016 KB ok, correct split
43 Correct 7 ms 1400 KB ok, correct split
44 Correct 7 ms 1404 KB ok, correct split
45 Correct 7 ms 1400 KB ok, correct split
46 Correct 5 ms 1272 KB ok, correct split
47 Correct 4 ms 1016 KB ok, no valid answer
48 Correct 6 ms 1400 KB ok, correct split
49 Correct 6 ms 1400 KB ok, correct split
50 Correct 2 ms 376 KB ok, no valid answer
51 Correct 2 ms 360 KB ok, no valid answer
52 Correct 6 ms 1400 KB ok, no valid answer
53 Correct 6 ms 1016 KB ok, no valid answer
54 Correct 5 ms 1272 KB ok, no valid answer
55 Correct 5 ms 1144 KB ok, no valid answer
56 Correct 5 ms 1144 KB ok, no valid answer

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB ok, correct split
2 Correct 2 ms 256 KB ok, correct split
3 Correct 2 ms 376 KB ok, correct split
4 Correct 2 ms 256 KB ok, correct split
5 Correct 2 ms 376 KB ok, correct split
6 Correct 2 ms 376 KB ok, correct split
7 Correct 353 ms 67136 KB ok, correct split
8 Correct 383 ms 63976 KB ok, correct split
9 Correct 347 ms 63136 KB ok, correct split
10 Correct 295 ms 72964 KB ok, correct split
11 Correct 278 ms 66784 KB ok, correct split
12 Correct 2 ms 256 KB ok, correct split
13 Correct 2 ms 376 KB ok, correct split
14 Correct 2 ms 376 KB ok, correct split
15 Correct 260 ms 52116 KB ok, correct split
16 Correct 305 ms 64032 KB ok, correct split
17 Correct 286 ms 72876 KB ok, correct split
18 Correct 355 ms 63768 KB ok, correct split
19 Correct 288 ms 45372 KB ok, correct split
20 Correct 177 ms 33640 KB ok, correct split
21 Correct 237 ms 61240 KB ok, correct split
22 Correct 215 ms 61408 KB ok, correct split
23 Correct 190 ms 61284 KB ok, correct split
24 Correct 2 ms 256 KB ok, correct split
25 Correct 318 ms 61084 KB ok, correct split
26 Correct 106 ms 26320 KB ok, correct split
27 Correct 3 ms 376 KB ok, correct split
28 Correct 343 ms 66524 KB ok, correct split
29 Correct 329 ms 66084 KB ok, correct split
30 Correct 373 ms 66916 KB ok, correct split
31 Correct 359 ms 67756 KB ok, correct split
32 Correct 366 ms 65740 KB ok, correct split
33 Correct 67 ms 13740 KB ok, no valid answer
34 Correct 132 ms 21420 KB ok, no valid answer
35 Correct 185 ms 38180 KB ok, no valid answer
36 Correct 244 ms 42380 KB ok, no valid answer
37 Correct 142 ms 36580 KB ok, no valid answer
38 Correct 2 ms 256 KB ok, correct split
39 Correct 2 ms 376 KB ok, no valid answer
40 Correct 2 ms 376 KB ok, correct split
41 Correct 2 ms 252 KB ok, correct split
42 Correct 2 ms 376 KB ok, correct split
43 Correct 2 ms 256 KB ok, correct split
44 Correct 2 ms 376 KB ok, correct split
45 Correct 2 ms 256 KB ok, correct split
46 Correct 6 ms 1144 KB ok, correct split
47 Correct 7 ms 1400 KB ok, correct split
48 Correct 2 ms 376 KB ok, correct split
49 Correct 7 ms 1528 KB ok, correct split
50 Correct 2 ms 376 KB ok, correct split
51 Correct 2 ms 256 KB ok, correct split
52 Correct 2 ms 376 KB ok, correct split
53 Correct 2 ms 376 KB ok, correct split
54 Correct 2 ms 376 KB ok, correct split
55 Correct 2 ms 376 KB ok, correct split
56 Correct 3 ms 632 KB ok, correct split
57 Correct 4 ms 860 KB ok, correct split
58 Correct 8 ms 1912 KB ok, correct split
59 Correct 8 ms 1912 KB ok, correct split
60 Correct 8 ms 2040 KB ok, correct split
61 Correct 8 ms 1912 KB ok, correct split
62 Correct 8 ms 2040 KB ok, correct split
63 Correct 7 ms 1784 KB ok, correct split
64 Correct 7 ms 1784 KB ok, correct split
65 Correct 7 ms 1784 KB ok, correct split
66 Correct 3 ms 504 KB ok, correct split
67 Correct 6 ms 1272 KB ok, correct split
68 Correct 3 ms 636 KB ok, correct split
69 Correct 3 ms 492 KB ok, correct split
70 Correct 3 ms 504 KB ok, correct split
71 Correct 8 ms 1912 KB ok, correct split
72 Correct 8 ms 1656 KB ok, correct split
73 Correct 8 ms 1784 KB ok, correct split
74 Correct 8 ms 1784 KB ok, correct split
75 Correct 8 ms 1784 KB ok, correct split
76 Correct 8 ms 1912 KB ok, correct split
77 Correct 8 ms 1784 KB ok, correct split
78 Correct 5 ms 1020 KB ok, correct split
79 Correct 5 ms 1016 KB ok, correct split
80 Correct 7 ms 1400 KB ok, correct split
81 Correct 7 ms 1404 KB ok, correct split
82 Correct 7 ms 1400 KB ok, correct split
83 Correct 5 ms 1272 KB ok, correct split
84 Correct 4 ms 1016 KB ok, no valid answer
85 Correct 6 ms 1400 KB ok, correct split
86 Correct 6 ms 1400 KB ok, correct split
87 Correct 2 ms 376 KB ok, no valid answer
88 Correct 2 ms 360 KB ok, no valid answer
89 Correct 6 ms 1400 KB ok, no valid answer
90 Correct 6 ms 1016 KB ok, no valid answer
91 Correct 5 ms 1272 KB ok, no valid answer
92 Correct 5 ms 1144 KB ok, no valid answer
93 Correct 5 ms 1144 KB ok, no valid answer
94 Correct 345 ms 63900 KB ok, correct split
95 Correct 387 ms 65104 KB ok, correct split
96 Correct 366 ms 63544 KB ok, correct split
97 Correct 110 ms 26968 KB ok, correct split
98 Correct 95 ms 23032 KB ok, correct split
99 Correct 95 ms 15308 KB ok, correct split
100 Correct 284 ms 47284 KB ok, correct split
101 Correct 303 ms 47544 KB ok, correct split
102 Correct 262 ms 49280 KB ok, correct split
103 Correct 237 ms 51648 KB ok, correct split
104 Correct 206 ms 39488 KB ok, correct split
105 Correct 192 ms 36132 KB ok, correct split
106 Correct 256 ms 63288 KB ok, correct split
107 Correct 330 ms 59852 KB ok, correct split
108 Correct 321 ms 59716 KB ok, correct split
109 Correct 275 ms 41908 KB ok, correct split
110 Correct 287 ms 57792 KB ok, correct split
111 Correct 303 ms 62556 KB ok, correct split
112 Correct 348 ms 58676 KB ok, correct split
113 Correct 315 ms 62876 KB ok, correct split
114 Correct 29 ms 6616 KB ok, correct split
115 Correct 27 ms 6360 KB ok, correct split
116 Correct 243 ms 44528 KB ok, correct split
117 Correct 242 ms 43272 KB ok, correct split
118 Correct 178 ms 32620 KB ok, correct split
119 Correct 198 ms 41244 KB ok, correct split
120 Correct 200 ms 40668 KB ok, correct split
121 Correct 221 ms 39184 KB ok, no valid answer
122 Correct 245 ms 43680 KB ok, no valid answer
123 Correct 177 ms 28652 KB ok, no valid answer
124 Correct 195 ms 28324 KB ok, no valid answer
125 Correct 168 ms 35168 KB ok, no valid answer
126 Correct 142 ms 34196 KB ok, no valid answer
127 Correct 161 ms 31284 KB ok, no valid answer