oj.uz

답안 #984318

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
984318 2024-05-16T13:15:52 Z michified Split the Attractions (IOI19_split) C++17
0 / 100
 0 ms 348 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.ord) {
				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;
				}
			}
		}
		good = false;
	} 
}

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, -1);
	if (not ok) {
		remain = thing[1].first;
		construct(found.first, 0, -1);
		remain = thing[0].first;
		construct(found.first, thing[0].second, -1);
		remain = thing[1].first;
		construct(found.second, thing[1].second, -1);
	} else {
		remain = thing[0].first;
		construct(found.second, thing[0].second, -1);
	}
	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:89:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for (i = 0; i < q.size(); i++) {
      |              ~~^~~~~~~~~~

Subtask #1
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 0 ms 348 KB ok, correct split
5 Correct 0 ms 348 KB ok, correct split
6 Incorrect 0 ms 348 KB invalid split: #1=20, #2=20, #3=60
7 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok, correct split
2 Correct 0 ms 348 KB ok, correct split
3 Incorrect 0 ms 348 KB invalid split: #1=1, #2=1, #3=3
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB invalid split: #1=1, #2=1, #3=3
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB invalid split: #1=6, #2=2, #3=1
2 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 0 ms 348 KB ok, correct split
5 Correct 0 ms 348 KB ok, correct split
6 Incorrect 0 ms 348 KB invalid split: #1=20, #2=20, #3=60
7 Halted 0 ms 0 KB -