oj.uz

Submission #984275

# Submission time Handle Problem Language Result Execution time Memory
984275 2024-05-16T12:27:09 Z michified Split the Attractions (IOI19_split) C++17
18 / 100
 138 ms 46428 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct node_t {
	int ord, low, ss, par;
	vector<int> adj;
	unordered_set<int> used;
};

vector<node_t> nodes;
vector<int> thing, ord2id, ans;
int lo, t = 0, n, remain;
bool good = true;
pair<int, int> found = {-1, -1};

void dfs(int cur, int par) {
	if (not good) return;
	node_t& u = nodes[cur];
	u.par = par;
	int mcss = 0;
	t++;
	u.ord = u.low = t;
	u.ss = 1;
	ord2id[t] = cur;
	for (int v : u.adj) {
		if (not nodes[v].ord) {
			dfs(v, cur);
			u.low = min(u.low, nodes[v].low);
			u.used.insert(v);
			nodes[v].used.insert(cur);
			u.ss += nodes[v].ss;
			mcss = max(mcss, nodes[v].ss);
		} else if (v != par) {
			u.low = min(u.low, nodes[v].ord);
		} 
	}
	if (found.first != -1) return;
	if (mcss < lo and u.ss >= lo) {
		if (par == -1) {
			good = false;
			return;
		}
		if (u.ss <= n - lo) {
			u.used.erase(par);
			nodes[par].used.erase(cur);
			found = make_pair(cur, par);
			return;
		}
		int curss = u.ss;
		for (int v : u.adj) {
			if (v == par) continue;
			if (nodes[v].low < u.low) {
				curss -= nodes[v].ss;
				u.used.erase(v);
				nodes[v].used.erase(cur);
				nodes[ord2id[nodes[v].low]].used.insert(v);
				nodes[v].used.insert(ord2id[nodes[v].low]);
				if (curss <= n - lo) { 
					found = make_pair(cur, par);
					return;
				}
			}
		}
	} 
}

bool construct(int cur, int group, int par) {
	if (remain == 0) return true;
	ans[cur] = group;
	remain--;
	bool res = false;
	for (int v : nodes[cur].used) {
		if (v == par) continue;
		res = res or construct(v, group, cur);
	}
	return res;
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
	int i;
	n = N;
	nodes.resize(n);
	ord2id.resize(n);
	lo = min(min(a, b), c);
	vector<pair<int, int>> thing = {{a, 1}, {b, 2}, {c, 3}};
	sort(thing.begin(), thing.end());
	for (i = 0; i < q.size(); i++) {
		nodes[p[i]].adj.push_back(q[i]);
		nodes[q[i]].adj.push_back(p[i]);
	}
	dfs(0, -1);
	ans.resize(n);
	if (not good) return ans;
	remain = thing[1].first;
	bool ok = construct(found.first, thing[1].second, found.second);
	if (not ok) {
		remain = thing[1].first;
		construct(found.first, 0, found.second);
		remain = thing[0].first;
		construct(found.first, thing[0].second, found.second);
		remain = thing[1].first;
		construct(found.second, thing[1].second, found.first);
	} else {
		remain = thing[0].first;
		construct(found.second, thing[0].second, found.first);
	}
	for (i = 0; i < n; i++) {
		if (ans[i] == 0) ans[i] = thing[2].second;
	}
	return ans;
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:88:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for (i = 0; i < q.size(); i++) {
      |              ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 1 ms 528 KB ok, correct split
3 Correct 1 ms 348 KB ok, correct split
4 Correct 0 ms 344 KB ok, correct split
5 Correct 1 ms 344 KB ok, correct split
6 Correct 0 ms 348 KB ok, correct split
7 Correct 133 ms 45824 KB ok, correct split
8 Correct 118 ms 42224 KB ok, correct split
9 Correct 118 ms 41044 KB ok, correct split
10 Correct 115 ms 46428 KB ok, correct split
11 Correct 126 ms 46416 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB ok, correct split
2 Correct 1 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 124 ms 41248 KB ok, correct split
5 Correct 113 ms 34132 KB ok, correct split
6 Correct 115 ms 46408 KB ok, correct split
7 Correct 132 ms 41820 KB ok, correct split
8 Correct 124 ms 36992 KB ok, correct split
9 Correct 122 ms 34020 KB ok, correct split
10 Correct 111 ms 35300 KB ok, correct split
11 Correct 113 ms 35416 KB ok, correct split
12 Correct 107 ms 35812 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 138 ms 34164 KB ok, correct split
3 Correct 33 ms 13976 KB ok, correct split
4 Runtime error 1 ms 344 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 1 ms 528 KB ok, correct split
3 Correct 1 ms 348 KB ok, correct split
4 Correct 0 ms 344 KB ok, correct split
5 Correct 1 ms 344 KB ok, correct split
6 Correct 0 ms 348 KB ok, correct split
7 Correct 133 ms 45824 KB ok, correct split
8 Correct 118 ms 42224 KB ok, correct split
9 Correct 118 ms 41044 KB ok, correct split
10 Correct 115 ms 46428 KB ok, correct split
11 Correct 126 ms 46416 KB ok, correct split
12 Correct 0 ms 344 KB ok, correct split
13 Correct 1 ms 348 KB ok, correct split
14 Correct 0 ms 348 KB ok, correct split
15 Correct 124 ms 41248 KB ok, correct split
16 Correct 113 ms 34132 KB ok, correct split
17 Correct 115 ms 46408 KB ok, correct split
18 Correct 132 ms 41820 KB ok, correct split
19 Correct 124 ms 36992 KB ok, correct split
20 Correct 122 ms 34020 KB ok, correct split
21 Correct 111 ms 35300 KB ok, correct split
22 Correct 113 ms 35416 KB ok, correct split
23 Correct 107 ms 35812 KB ok, correct split
24 Correct 0 ms 348 KB ok, correct split
25 Correct 138 ms 34164 KB ok, correct split
26 Correct 33 ms 13976 KB ok, correct split
27 Runtime error 1 ms 344 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -