이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
int par[100005], sz[100005], sztree[100005];
vector<int> graph[100005], tree[100005], inter[100005];
pair<int, int> info[3];
int findset(int i) {
return (i == par[i] ? i : par[i] = findset(par[i]));
}
bool onion(int a, int b) {
a = findset(a), b = findset(b);
if (a == b) return false;
if (sz[a] < sz[b]) swap(a, b);
par[b] = a;
sz[a] += sz[b];
return true;
}
void dfscent(int node, int par = -1) {
sztree[node] = 1;
for (auto nxt : tree[node]) {
if (nxt == par) continue;
dfscent(nxt, node);
sztree[node] += sz[nxt];
}
}
int centroid(int node, int par = -1) {
for (auto nxt : tree[node]) {
if (nxt == par) continue;
if (sztree[nxt] * 2 > sz[0]) return centroid(nxt, node);
}
return node;
}
vector<int> nodes;
void dfs(int node, int par) {
nodes.push_back(node);
for (auto nxt : graph[node]) {
if (nxt == par) continue;
onion(nxt, node);
dfs(nxt, node);
}
}
int state[100005];
bool createseen[100005];
vector<int> ansnodes;
void dfscreate(int node) {
ansnodes.push_back(node);
createseen[node] = true;
for (auto nxt : graph[node]) {
if (!createseen[nxt] && state[nxt] == state[node]) dfscreate(nxt);
}
}
vector<int> create() {
vector<int> ans(n, info[2].second);
for (auto cur : nodes) {
state[cur] = 1;
}
for (int i = 0; i < n; i++) {
if (state[i] == 1 && !createseen[i]) {
ansnodes.clear();
dfscreate(i);
for (int j = 0; j < info[0].first; j++) {
ans[ansnodes[j]] = info[0].second;
}
}
if (state[i] == 0 && !createseen[i]) {
ansnodes.clear();
dfscreate(i);
for (int j = 0; j < info[1].first; j++) {
ans[ansnodes[j]] = info[1].second;
}
}
}
return ans;
}
bool seen[100005];
vector<int> across;
void dfsacross(int node) {
across.push_back(node);
seen[node] = true;
for (auto nxt : inter[node]) {
if (!seen[nxt]) dfsacross(nxt);
}
}
vector<int> find_split(int _n, int a, int b, int c, vector<int> p, vector<int> q) {
n = _n; m = p.size();
info[0] = {a, 0};
info[1] = {b, 1};
info[2] = {c, 2};
sort(info, info + 3);
for (int i = 0; i < n; i++) {
par[i] = i; sz[i] = 1;
}
for (int i = 0; i < m; i++) {
graph[p[i]].push_back(q[i]);
graph[q[i]].push_back(p[i]);
if (onion(p[i], q[i])) {
tree[p[i]].push_back(q[i]);
tree[q[i]].push_back(p[i]);
}
}
dfscent(0);
int cent = centroid(0);
for (int i = 0; i < n; i++) {
par[i] = i; sz[i] = 1;
}
for (auto nxt : tree[cent]) {
nodes.clear();
dfs(nxt, cent);
if (nodes.size() >= info[0].first) {
// rest are connected
return create();
}
}
vector<int> asdf(1000000000000, 0);
for (int i = 0; i < m; i++) {
if (p[i] == cent || q[i] == cent) continue;
int a = findset(p[i]), b = findset(q[i]);
if (a == b) continue;
inter[a].push_back(b);
inter[b].push_back(a);
}
for (int i = 0; i < n; i++) {
if (findset(i) == i && i != c && !seen[i]) {
across.clear();
dfsacross(i);
int ct = 0;
set<int> used;
for (auto tre : across) {
ct += sz[findset(tre)];
used.insert(tre);
if (ct >= info[0].first) break;
}
if (ct >= info[0].first) {
nodes.clear();
for (int j = 0; j < n; j++) {
if (used.count(findset(j))) nodes.push_back(j);
}
return create();
}
}
}
return vector<int> (n, 0);
}
컴파일 시 표준 에러 (stderr) 메시지
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:149:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
149 | if (nodes.size() >= info[0].first) {
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
# | 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... |