이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <queue>
#include <cassert>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair <int, int> pii;
#define TRACE(x) cerr << #x << ' ' << x << endl
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define fi first
#define sec second
#define pb push_back
const int MAXN = 200100;
int n;
vector <int> v[MAXN];
vector <int> bio;
bool bfs(int start, vector <int> boje, vector <int> &ret) {
queue <int> q;
bio[start] = 1;
int cnt = 0;
q.push(start);
vector <int> pos;
while (!q.empty()) {
int cvor = q.front();
q.pop();
cnt++;
pos.pb(cvor);
if (cnt == min(boje[2], boje[3])) {
int boja = 3;
if (boje[3] > boje[2]) boja = 2;
for (auto &x : pos) ret[x] = boja;
return true;
}
for (auto &ncvor : v[cvor]) {
if (bio[ncvor]) continue;
bio[ncvor] = 1;
q.push(ncvor);
}
}
return false;
}
vector <int> solve1(vector <int> boje) {
vector <int> ret;
ret.resize(n);
REP(i, n) {
if (bio[i]) continue;
if (bfs(i, boje, ret)) {
int boja = 2;
if (boje[3] > boje[2]) boja = 3;
REP(j, n) {
if (ret[j] == 0 && boje[1]) {
ret[j] = 1;
boje[1]--;
} else if (ret[j] == 0) ret[j] = boja;
}
return ret;
}
}
return ret;
}
int sub[MAXN];
void dfs(int cvor, int par) {
sub[cvor]++;
for (auto &ncvor : v[cvor]) {
if (ncvor == par) continue;
dfs(ncvor, cvor);
sub[cvor] += sub[ncvor];
}
}
void bojaj(int cvor, int par, int boja, vector <int> &boje, vector <int> &ret) {
if (boje[boja] == 0) return;
ret[cvor] = boja;
boje[boja]--;
for (auto &ncvor : v[cvor]) {
if (par == ncvor) continue;
bojaj(ncvor, cvor, boja, boje, ret);
}
}
vector <int> rezi(int A, int B, vector <int> boje, int ka, int kb) {
vector <int> ret;
ret.resize(n);
bojaj(A, B, ka, boje, ret);
bojaj(B, A, kb, boje, ret);
REP(i, n) if (!ret[i]) ret[i] = 6 - ka - kb;
return ret;
}
vector <int> stablo(vector <int> boje) {
dfs(0, -1);
vector <pii> B;
FOR(i, 1, 4) B.pb({boje[i], i});
sort(B.begin(), B.end());
REP(i, MAXN) {
for (auto &j : v[i]) {
int x = i, y = j;
if (sub[x] > sub[y]) swap(x, y);
int ostalo = n - sub[x];
if (ostalo >= B[0].fi && sub[x] >= B[1].fi) {
return rezi(y, x, boje, B[0].sec, B[1].sec);
}
if (ostalo >= B[1].fi && sub[x] >= B[0].fi) {
return rezi(x, y, boje, B[0].sec, B[1].sec);
}
}
}
vector <int> ret;
ret.resize(n);
return ret;
}
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
n = N;
bio.resize(n);
REP(i, p.size()) {
v[p[i]].pb(q[i]);
v[q[i]].pb(p[i]);
}
vector <int> boje = {0, a, b, c};
if (p.size() == n - 1) return stablo(boje);
return solve1(boje);
}
컴파일 시 표준 에러 (stderr) 메시지
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:13:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
| ^
split.cpp:14:19: note: in expansion of macro 'FOR'
14 | #define REP(i, n) FOR(i, 0, n)
| ^~~
split.cpp:137:3: note: in expansion of macro 'REP'
137 | REP(i, p.size()) {
| ^~~
split.cpp:142:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
142 | if (p.size() == n - 1) return stablo(boje);
| ~~~~~~~~~^~~~~~~~
# | 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... |