oj.uz

답안 #984287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
984287 2024-05-16T12:41:29 Z michified Split the Attractions (IOI19_split) C++17
18 / 100
 169 ms 45580 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 + 1);
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 1 ms 348 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Correct 0 ms 344 KB ok, correct split
7 Correct 116 ms 44672 KB ok, correct split
8 Correct 136 ms 41092 KB ok, correct split
9 Correct 125 ms 39912 KB ok, correct split
10 Correct 118 ms 45580 KB ok, correct split
11 Correct 136 ms 45492 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok, correct split
2 Correct 1 ms 344 KB ok, correct split
3 Correct 1 ms 348 KB ok, correct split
4 Correct 135 ms 39460 KB ok, correct split
5 Correct 114 ms 33000 KB ok, correct split
6 Correct 124 ms 45396 KB ok, correct split
7 Correct 98 ms 40884 KB ok, correct split
8 Correct 120 ms 34900 KB ok, correct split
9 Correct 169 ms 32844 KB ok, correct split
10 Correct 101 ms 35264 KB ok, correct split
11 Correct 104 ms 35300 KB ok, correct split
12 Correct 100 ms 35220 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 124 ms 33652 KB ok, correct split
3 Correct 31 ms 13908 KB ok, correct split
4 Correct 0 ms 348 KB ok, correct split
5 Correct 155 ms 38116 KB ok, correct split
6 Correct 153 ms 37808 KB ok, correct split
7 Correct 131 ms 37460 KB ok, correct split
8 Correct 128 ms 39652 KB ok, correct split
9 Correct 100 ms 37104 KB ok, correct split
10 Runtime error 24 ms 14832 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, no valid answer
3 Correct 0 ms 348 KB ok, correct split
4 Correct 1 ms 348 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Correct 1 ms 348 KB ok, correct split
7 Correct 1 ms 348 KB ok, correct split
8 Correct 0 ms 348 KB ok, correct split
9 Correct 2 ms 1116 KB ok, correct split
10 Correct 3 ms 1116 KB ok, correct split
11 Correct 0 ms 348 KB ok, correct split
12 Correct 2 ms 1116 KB ok, correct split
13 Correct 0 ms 348 KB ok, correct split
14 Correct 0 ms 344 KB ok, correct split
15 Correct 0 ms 348 KB ok, correct split
16 Correct 0 ms 348 KB ok, correct split
17 Correct 0 ms 344 KB ok, correct split
18 Correct 0 ms 348 KB ok, correct split
19 Correct 1 ms 604 KB ok, correct split
20 Correct 1 ms 604 KB ok, correct split
21 Correct 2 ms 1372 KB ok, correct split
22 Correct 2 ms 1360 KB ok, correct split
23 Correct 2 ms 1240 KB ok, correct split
24 Correct 2 ms 1372 KB ok, correct split
25 Correct 2 ms 1372 KB ok, correct split
26 Runtime error 3 ms 2140 KB Execution killed with signal 11
27 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Correct 0 ms 348 KB ok, correct split
4 Correct 1 ms 348 KB ok, correct split
5 Correct 1 ms 348 KB ok, correct split
6 Correct 0 ms 344 KB ok, correct split
7 Correct 116 ms 44672 KB ok, correct split
8 Correct 136 ms 41092 KB ok, correct split
9 Correct 125 ms 39912 KB ok, correct split
10 Correct 118 ms 45580 KB ok, correct split
11 Correct 136 ms 45492 KB ok, correct split
12 Correct 0 ms 344 KB ok, correct split
13 Correct 1 ms 344 KB ok, correct split
14 Correct 1 ms 348 KB ok, correct split
15 Correct 135 ms 39460 KB ok, correct split
16 Correct 114 ms 33000 KB ok, correct split
17 Correct 124 ms 45396 KB ok, correct split
18 Correct 98 ms 40884 KB ok, correct split
19 Correct 120 ms 34900 KB ok, correct split
20 Correct 169 ms 32844 KB ok, correct split
21 Correct 101 ms 35264 KB ok, correct split
22 Correct 104 ms 35300 KB ok, correct split
23 Correct 100 ms 35220 KB ok, correct split
24 Correct 1 ms 348 KB ok, correct split
25 Correct 124 ms 33652 KB ok, correct split
26 Correct 31 ms 13908 KB ok, correct split
27 Correct 0 ms 348 KB ok, correct split
28 Correct 155 ms 38116 KB ok, correct split
29 Correct 153 ms 37808 KB ok, correct split
30 Correct 131 ms 37460 KB ok, correct split
31 Correct 128 ms 39652 KB ok, correct split
32 Correct 100 ms 37104 KB ok, correct split
33 Runtime error 24 ms 14832 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -