이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 1e5 + 7;
vi G[N];
vi T[N];
vi find_split(int n, int a, int b, int c, vi p, vi q) {
int m = SZ(p);
for(int i = 0; i < m; i++) {
int u = p[i], v = q[i];
G[u].PB(v);
G[v].PB(u);
}
assert(a + b + c == n);
pi aux[] = {pi(a, 1), pi(b, 2), pi(c, 3)};
sort(aux, aux + 3);
V<bool> vis(n);
function<void(int)> dfs = [&] (int u) {
vis[u] = true;
for(int v:G[u]) if(!vis[v]) {
T[u].PB(v);
dfs(v);
}
};
dfs(0);
vi ans(n);
bool flag = false;
function<int(int)> dfs2 = [&] (int u) {
int sz = 1;
for(int v:T[u]) {
int tt = dfs2(v);
function<void(int, int&, int)> mark = [&] (int uu, int& need, int id) {
if(!need) return;
ans[uu] = id;
need--;
for(int vv:T[uu]) if(vv != v) {
mark(vv, need, id);
}
};
if(!flag && tt >= aux[0].F && n - tt >= aux[1].F) {
ans = vi(n, aux[0].S ^ aux[1].S);
mark(v, aux[0].F, aux[0].S);
mark(0, aux[1].F, aux[1].S);
assert(aux[0].F == 0);
assert(aux[1].F == 0);
flag = true;
}
if(!flag && tt >= aux[1].F && n - tt >= aux[0].F) {
ans = vi(n, aux[0].S ^ aux[1].S);
mark(v, aux[1].F, aux[1].S);
mark(0, aux[0].F, aux[0].S);
assert(aux[0].F == 0);
assert(aux[1].F == 0);
flag = true;
}
sz += tt;
}
return sz;
};
dfs2(0);
return ans;
}
# | 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... |