QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#348387 | #8130. Yet Another Balanced Coloring Problem | SpaceJellyfish | TL | 80ms | 165704kb | C++20 | 5.9kb | 2024-03-09 18:09:56 | 2024-03-09 18:09:56 |
Judging History
answer
#include <cstring>
#include <functional>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
const int N = 2e5 + 10, M = 20 * N, INF = 0x3f3f3f3f;
int T, n, m;
vector<int> getsz(int n, const vector<vector<int>> &g) {
vector<int> sz(n + 1);
function<void(int)> dfs = [&](int u) {
if (g[u].empty()) {
sz[u] = 1;
return;
}
for (int v : g[u]) {
dfs(v);
sz[u] += sz[v];
}
};
dfs(n);
return sz;
}
int s, t;
struct qxx {
int nex, t, v;
};
qxx e[M];
int h[N], cnt;
void addedge(int f, int t, int v) { e[++cnt] = (qxx){h[f], t, v}, h[f] = cnt; }
int ht[N + 1], ex[N + 1],
gap[N]; // 高度; 超额流; gap 优化 gap[i] 为高度为 i 的节点的数量
stack<int> B[N]; // 桶 B[i] 中记录所有 ht[v]==i 的v
int level; // 溢出节点的最高高度
int push(int u) { // 尽可能通过能够推送的边推送超额流
bool init = u == s; // 是否在初始化
for (int i = h[u]; i; i = e[i].nex) {
const int &v = e[i].t, &w = e[i].v;
if (!w || init == false && ht[u] != ht[v] + 1 ||
ht[v] == INF) // 初始化时不考虑高度差为1
continue;
int k = init ? w : min(w, ex[u]);
// 取到剩余容量和超额流的最小值,初始化时可以使源的溢出量为负数。
if (v != s && v != t && !ex[v])
B[ht[v]].push(v), level = max(level, ht[v]);
ex[u] -= k, ex[v] += k, e[i].v -= k, e[i ^ 1].v += k; // push
if (!ex[u])
return 0; // 如果已经推送完就返回
}
return 1;
}
void relabel(int u) { // 重贴标签(高度)
ht[u] = INF;
for (int i = h[u]; i; i = e[i].nex)
if (e[i].v)
ht[u] = min(ht[u], ht[e[i].t]);
if (++ht[u] < t) { // 只处理高度小于 n 的节点
B[ht[u]].push(u);
level = max(level, ht[u]);
++gap[ht[u]]; // 新的高度,更新 gap
}
}
bool bfs_init() {
memset(ht, 0x3f, sizeof(int) * (t + 1));
queue<int> q;
q.push(t), ht[t] = 0;
while (q.size()) { // 反向 BFS, 遇到没有访问过的结点就入队
int u = q.front();
q.pop();
for (int i = h[u]; i; i = e[i].nex) {
const int &v = e[i].t;
if (e[i ^ 1].v && ht[v] > ht[u] + 1)
ht[v] = ht[u] + 1, q.push(v);
}
}
return ht[s] != INF; // 如果图不连通,返回 0
}
int select() {
while (B[level].size() == 0 && level > -1)
level--;
return level == -1 ? 0 : B[level].top();
}
int hlpp() { // 返回最大流
if (!bfs_init())
return 0; // 图不连通
memset(gap, 0, sizeof(int) * (t + 1));
for (int i = 1; i <= t; i++)
if (ht[i] != INF)
gap[ht[i]]++; // 初始化 gap
ht[s] = t;
push(s); // 初始化预流
int u;
while ((u = select())) {
B[level].pop();
if (push(u)) { // 仍然溢出
if (!--gap[ht[u]])
for (int i = 1; i <= t; i++)
if (i != s && ht[i] > ht[u] && ht[i] < t + 1)
ht[i] = t + 1; // 这里重贴成 n+1 的节点都不是溢出节点
relabel(u);
}
}
return ex[t];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--) {
level = 0;
cnt = 1;
cin >> n >> m;
s = n + m + 1;
t = n + m + 2;
memset(h + 1, 0, sizeof(int) * t);
memset(ex + 1, 0, sizeof(int) * t);
vector<vector<int>> g(n + 1), h(m + 1);
vector<int> gfa(n + 1), hfa(m + 1);
for (int i = 1; i < n; i++) {
int p;
cin >> p;
gfa[i] = p;
g[p].emplace_back(i);
}
for (int i = 1; i < m; i++) {
int q;
cin >> q;
hfa[i] = q;
h[q].emplace_back(i);
}
vector<int> gsz = getsz(n, g);
vector<int> hsz = getsz(m, h);
int k = gsz[n];
for (int i = 1; i < n; i++) {
if (gsz[i] & 1) {
addedge(i, gfa[i], 1);
addedge(gfa[i], i, 0);
}
}
if (k & 1) {
addedge(n, n + m, 1);
addedge(n + m, n, 0);
}
for (int i = 1; i < m; i++) {
if (hsz[i] & 1) {
addedge(n + hfa[i], n + i, 1);
addedge(n + i, n + hfa[i], 0);
}
}
vector<int> cid(k + 1);
for (int i = 1; i <= k; i++) {
addedge(n + i, i, 1);
addedge(i, n + i, 0);
cid[i] = cnt;
}
int expect = 0;
for (int i = k + 1; i <= n; i++) {
int sum = 0;
for (int j : g[i])
sum += gsz[j] >> 1;
sum -= gsz[i] >> 1;
if (sum > 0) {
expect += sum;
addedge(s, i, sum);
addedge(i, s, 0);
} else if (sum < 0) {
addedge(i, t, -sum);
addedge(t, i, 0);
}
}
for (int i = k + 1; i <= m; i++) {
int sum = hsz[i] >> 1;
for (int j : h[i])
sum -= hsz[j] >> 1;
if (sum > 0) {
expect += sum;
addedge(s, n + i, sum);
addedge(n + i, s, 0);
} else if (sum < 0) {
addedge(n + i, t, -sum);
addedge(t, n + i, 0);
}
}
if (hlpp() != expect) {
cout << "IMPOSSIBLE\n";
continue;
}
for (int i = 1; i <= k; i++)
cout << (e[cid[i]].v ? 'R' : 'B');
cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 20ms
memory: 141980kb
input:
2 7 7 5 5 6 6 7 7 5 6 5 6 7 7 5 4 4 4 5 5 4 4 4
output:
BRRB BRB
result:
ok ok (2 test cases)
Test #2:
score: 0
Accepted
time: 43ms
memory: 141636kb
input:
10000 6 6 5 5 5 5 6 5 6 6 6 6 9 6 7 9 7 7 6 8 9 9 6 6 6 6 6 9 8 9 9 8 7 7 8 8 9 7 7 8 7 7 7 8 6 10 4 5 5 6 6 4 6 5 7 8 9 8 9 10 6 9 6 6 6 6 6 6 9 7 8 8 9 9 9 8 9 8 6 6 7 6 7 8 7 9 7 6 7 8 9 9 9 8 6 7 7 5 8 8 8 9 7 5 6 5 8 7 8 8 7 6 6 5 5 6 7 8 5 7 6 6 7 7 9 9 8 9 8 8 8 8 9 9 9 9 8 8 9 9 8 9 9 8 8 8 ...
output:
BBRR BBRRB BRRRBB BBR BRBBR BRBBR RRBB BRBR BBBBRRR BBBBRRR BRB BRBBRR BBR BRBRBBR BBBRRR RBBR BBR BBBRR BBR RBBRB BRRBB BRRB BBBRR BBR BBRRB BBRR BRBRRB BBBRRR BRBR BBRRBR BBRBRR BBBRR BBBRRR BBRBRR RBRBRB RBB RBBR RBB BBR BBBRR BRRB BBBRRR BBR BRRBB RBB BBBRRR RBBRRB BRB BBBRRR BRB RBB BBRR BRBBR ...
result:
ok ok (10000 test cases)
Test #3:
score: 0
Accepted
time: 52ms
memory: 142212kb
input:
1000 98 96 41 39 52 47 34 37 45 33 68 54 74 35 65 58 49 46 53 42 87 30 43 48 38 36 56 40 88 66 32 31 72 44 91 96 51 85 83 61 60 59 80 63 70 80 75 61 51 83 50 69 86 55 79 62 67 57 73 93 96 64 69 91 78 73 80 83 81 91 91 71 76 81 75 90 92 77 82 89 82 86 98 84 96 89 97 96 91 97 94 93 95 97 97 95 96 97 9...
output:
RBRBBRBRRRBRBRBBRBBBBBRBRBRRR BRBRBBRRBBBRBBRRBRRBBRRR RBBBBBRBBBBBBBBBBBRBRBBRRBBRRBBRRRRRRRRRRRRRRRBRBRRRRBRBRRRBRBRRBBRRBBBRRBBBBRB RRBBBBBRBBBBRRRRRBRRBRRBB BBBRRBBRBRRBBBBRBRRRBRBRRRRBRRBBRBBRBBBRRRRRRBBBBR RRRBBRRRBRBRRBBRBRBBBBRBBRRBBRBRRRBB BBBBBBRBRBBRBRRBRRBBBRRBRRRRBRRBBRRRBR RBRBBRB RRBB...
result:
ok ok (1000 test cases)
Test #4:
score: 0
Accepted
time: 80ms
memory: 143316kb
input:
10 9442 9473 6729 7355 6467 7301 7964 7025 7066 7206 8711 8044 7401 6634 6594 9405 7767 7253 7611 6730 6630 8250 6872 6720 8868 8644 9280 7272 6808 8887 7965 7384 6376 9115 8340 7618 8377 9351 8690 8842 9014 6913 7207 7552 8087 9013 9340 6509 8152 6963 8666 8716 7681 6447 8097 7014 6854 8576 6915 92...
output:
RRRBRRRRBRBRRBRBBRRRBRBRBBBBRBRRBRBBRRBBBRBBBBBRBBRRBBBBBBRBRBRBBBRBRRRRBRBBBBBRBBBRRBRBRBBRBRRBBRRRBRBBBRBBRRBBBBRBRBBRBRRBBRRRBBRRRRBRBRRBRRRRBRBBRBRBRBRBRRRBBBRRRRRRBRRBRRRRRRRBBRRRBBRRBRBRBBBBBBBBBRBRBBBRBRRRRBBBRRBBBBBRBRRRBRBRBRBBBRRBRRBBBRRRBBRRBBRRBRBRRBRRRRBBRRRBRBBBBBBRBBBRBRRRBBBBBBBRRRRR...
result:
ok ok (10 test cases)
Test #5:
score: 0
Accepted
time: 56ms
memory: 165704kb
input:
1 100000 100000 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
output:
B
result:
ok ok (1 test case)
Test #6:
score: -100
Time Limit Exceeded
input:
1 100000 100000 27 17 44 12 22 19 14 21 15 11 48 13 16 20 34 18 24 26 25 28 43 23 33 29 31 30 46 45 41 36 32 38 90 35 40 37 39 55 47 42 59 52 65 72 49 50 54 53 51 64 56 57 66 58 63 82 62 61 60 69 86 95 85 71 68 67 83 70 74 73 77 75 81 76 78 88 89 79 80 84 94 96 123 106 110 87 92 91 99 102 93 98 101 ...