| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 941460 | Programmer123 | Split the Attractions (IOI19_split) | C++17 | 1952 ms | 19652 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <bits/stdc++.h>
std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
auto start_t = clock();
std::vector<int> res(n);
std::vector<int> connections[n];
for (int i = 0; i < p.size(); ++i) {
connections[p[i]].push_back(q[i]);
connections[q[i]].push_back(p[i]);
}
bool s1 = true;
for (int i = 0; i < n; ++i) {
if (connections[i].size() > 2) s1 = false;
}
if (s1) {
int start = 0;
for (int i = 0; i < n; ++i) {
if (connections[i].size() == 1) {
start = i;
break;
}
}
std::vector<int> order;
while (order.size() < n) {
order.push_back(start);
int next = connections[start][0];
if (connections[next].size() == 2 && connections[next][0] == start) {
std::swap(connections[next][0], connections[next][1]);
}
start = next;
}
for (int i = 0; i < a; ++i) {
res[order[i]] = 1;
}
for (int i = a; i < a + b; ++i) {
res[order[i]] = 2;
}
for (int i = a + b; i < n; ++i) {
res[order[i]] = 3;
}
} else if (a == 1) {
std::queue<int> bfs;
bfs.push(0);
res[0] = 2;
int rem = b - 1;
while (!bfs.empty()) {
auto next = bfs.front();
bfs.pop();
for (auto x: connections[next]) {
if (!rem) break;
if (res[x]) continue;
res[x] = 2;
bfs.push(x);
rem--;
}
}
for (int i = 0; i < n; ++i) {
if (res[i] == 0) {
res[i] = 1;
break;
}
}
for (int i = 0; i < n; ++i) {
if (res[i] == 0) res[i] = 3;
}
} else if (p.size() == n - 1) {
int size[n];
int parent[n];
std::vector<int> children[n];
std::function<int(int, int)> dfs = [&](int node, int from) {
parent[node] = from;
int res = 1;
for (auto x: connections[node]) {
if (x == from) continue;
children[node].push_back(x);
res += dfs(x, node);
}
return size[node] = res;
};
dfs(0, 0);
std::function<int(int, int, int)> fill = [&](int node, int num, int type) {
if (num == 0) return 0;
num--;
res[node] = type;
for (auto x: children[node]) {
num = fill(x, num, type);
}
return num;
};
std::function<void(int, int, int)> expand = [&](int node, int num, int type) {
std::queue<int> bfs;
bfs.push(node);
res[node] = type;
int rem = num - 1;
while (!bfs.empty()) {
auto next = bfs.front();
bfs.pop();
for (auto x: connections[next]) {
if (!rem) break;
if (res[x]) continue;
res[x] = type;
bfs.push(x);
rem--;
}
}
};
std::function<void(int)> fix = [&](int type) {
for (int i = 0; i < n; ++i) {
if (res[i] == 0) res[i] = type;
}
};
for (int i = 0; i < n; ++i) {
int s = size[i];
int so = n - size[i];
if (s >= a) {
if (so >= b) {
fill(i, a, 1);
expand(parent[i], b, 2);
fix(3);
return res;
}
if (so > c) {
fill(i, a, 1);
expand(parent[i], c, 3);
fix(2);
return res;
}
}
if (s >= b) {
if (so >= a) {
fill(i, b, 2);
expand(parent[i], a, 1);
fix(3);
return res;
}
if (so > c) {
fill(i, b, 2);
expand(parent[i], c, 3);
fix(1);
return res;
}
}
if (s >= c) {
if (so >= b) {
fill(i, c, 3);
expand(parent[i], b, 2);
fix(1);
return res;
}
if (so > a) {
fill(i, c, 3);
expand(parent[i], a, 1);
fix(2);
return res;
}
}
}
} else {
std::mt19937 Rand(std::random_device{}());
std::uniform_int_distribution dist(0, n - 1);
while (clock() - start_t <= 1.95 * CLOCKS_PER_SEC) {
if (Rand() % 2) {
int root = dist(Rand);
for (int i = 0; i < n; ++i) {
std::shuffle(connections[i].begin(), connections[i].end(), std::default_random_engine(Rand()));
}
int size[n];
int parent[n];
std::vector<int> children[n];
bool seen[n];
for (int i = 0; i < n; ++i) {
seen[i] = false;
}
std::function<void(int)> Root = [&](int node) {
parent[node] = node;
seen[node] = true;
if (Rand() % 2) {
std::queue<int> queue;
queue.push(node);
while (!queue.empty()) {
auto next = queue.front();
queue.pop();
for (auto x: connections[next]) {
if (seen[x]) continue;
seen[x] = true;
parent[x] = next;
children[next].push_back(x);
queue.push(x);
}
}
} else {
std::stack<int> queue;
queue.push(node);
while (!queue.empty()) {
auto next = queue.top();
queue.pop();
for (auto x: connections[next]) {
if (seen[x]) continue;
seen[x] = true;
parent[x] = next;
children[next].push_back(x);
queue.push(x);
}
}
}
// seen[node] = true;
// parent[node] = from;
// int res = 1;
// for (auto x: connections[node]) {
// if (seen[x]) continue;
// children[node].push_back(x);
// res += dfs(x, node);
// }
// return size[node] = res;
};
std::function<int(int, int)> oldroot = [&](int node, int from) {
seen[node] = true;
parent[node] = from;
int res = 1;
for (auto x: connections[node]) {
if (seen[x]) continue;
children[node].push_back(x);
res += oldroot(x, node);
}
return size[node] = res;
};
std::function<int(int)> dfs = [&](int node) {
int s = 1;
for (auto x: children[node]) {
s += dfs(x);
}
return size[node] = s;
};
if (Rand() % 2) {
Root(root);
dfs(root);
} else {
oldroot(root, root);
}
std::function<int(int, int, int)> fill = [&](int node, int num, int type) {
if (num == 0) return 0;
num--;
res[node] = type;
for (auto x: children[node]) {
num = fill(x, num, type);
}
return num;
};
std::function<void(int, int, int)> expand = [&](int node, int num, int type) {
std::queue<int> bfs;
bfs.push(node);
res[node] = type;
int rem = num - 1;
while (!bfs.empty()) {
auto next = bfs.front();
bfs.pop();
for (auto x: connections[next]) {
if (!rem) break;
if (res[x]) continue;
res[x] = type;
bfs.push(x);
rem--;
}
}
};
std::function<void(int)> fix = [&](int type) {
for (int i = 0; i < n; ++i) {
if (res[i] == 0) res[i] = type;
}
};
for (int i = 0; i < n; ++i) {
int s = size[i];
int so = n - size[i];
if (s >= a) {
if (so >= b) {
fill(i, a, 1);
expand(parent[i], b, 2);
fix(3);
return res;
}
if (so > c) {
fill(i, a, 1);
expand(parent[i], c, 3);
fix(2);
return res;
}
}
if (s >= b) {
if (so >= a) {
fill(i, b, 2);
expand(parent[i], a, 1);
fix(3);
return res;
}
if (so > c) {
fill(i, b, 2);
expand(parent[i], c, 3);
fix(1);
return res;
}
}
if (s >= c) {
if (so >= b) {
fill(i, c, 3);
expand(parent[i], b, 2);
fix(1);
return res;
}
if (so > a) {
fill(i, c, 3);
expand(parent[i], a, 1);
fix(2);
return res;
}
}
}
} else {
int num1, t1, num2, t2;
do {
switch (Rand() % 3) {
case 0:
num1 = a;
t1 = 1;
break;
case 1:
num1 = b;
t1 = 2;
break;
case 2:
num1 = c;
t1 = 3;
break;
}
switch (Rand() % 3) {
case 0:
num2 = a;
t2 = 1;
break;
case 1:
num2 = b;
t2 = 2;
break;
case 2:
num2 = c;
t2 = 3;
break;
}
} while (t1 == t2);
int r1, r2;
do {
r1 = Rand() % n;
r2 = Rand() % n;
} while (r1 == r2);
num1--;
num2--;
res[r1] = t1;
res[r2] = t2;
std::queue<int> q1, q2;
q1.push(r1);
q2.push(r2);
while (true) {
if (num1 + num2 == 0) {
for (int i = 0; i < n; ++i) {
if (res[i] == 0) res[i] = 6 - t1 - t2;
}
return res;
}
if (num1 && q1.empty()) {
break;
}
if (num2 && q2.empty()) {
break;
}
if (num1 > num2) {
auto next = q1.front();
q1.pop();
for (auto x: connections[next]) {
if (!num1) break;
if (res[x] != 0) break;
res[x] = t1;
num1--;
q1.push(x);
}
} else {
auto next = q2.front();
q2.pop();
for (auto x: connections[next]) {
if (!num2) break;
if (res[x] != 0) break;
res[x] = t2;
num2--;
q2.push(x);
}
}
}
res = std::vector<int>(n);
}
}
}
return res;
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||