QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#348404 | #8130. Yet Another Balanced Coloring Problem | SpaceJellyfish | TL | 197ms | 26784kb | C++20 | 5.8kb | 2024-03-09 18:15:48 | 2024-03-09 18:15:49 |
Judging History
answer
#include <cstring>
#include <functional>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
const int N = 1e5 + 10;
int T, n, m;
vector<int> getsz(int n, const vector<vector<int>> &g) {
vector<int> sz(n + 1);
for (int i = 1; i <= n; i++) {
if(g[i].empty())
sz[i] = 1;
for(int j : g[i])
sz[i] += sz[j];
}
return sz;
}
int s, t, cnt, head[N * 2];
struct Node
{
int v;//当前点
int next;//连接点
int val;//容量
}node[N * 40];//node[i]:第i条边的情况
inline void addedge(int u,int v,int val)
{
node[++cnt].v=v;
node[cnt].val=val;
node[cnt].next=head[u];
head[u]=cnt;
}
int dep[N * 2],gap[N * 2];//dep[i]表示节点i的深度,gap[i]表示深度为i的点的数量
void bfs()//倒着搜
{
memset(dep,-1,sizeof(int) * (t + 1));//把深度变为-1(0会导致gap崩坏)
memset(gap,0,sizeof(int) * (t + 1));
dep[t]=0;//汇点深度为0
gap[0]=1;//深度为0的点有1个
queue<int>q;
q.push(t);//t点入栈
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=node[i].next)//head[u]:u点所在的边,node[i].next:u点所在的边的下一个点,就这样遍历下去
{
int v=node[i].v;//v为当前边的下一个点
if(dep[v]!=-1) continue;//dep[v]!=-1相当于v点已被遍历||不管
q.push(v);
dep[v]=dep[u]+1;//v点的深度比u点大1
gap[dep[v]]++;
}//直到所有点都被遍历过
}
return;
}//从t到s跑一遍bfs,标记深度
long long maxflow;
int dfs(int u,int flow)
{
if(u==t)
{
maxflow+=flow;
return flow;
}
int used=0;
for(int i=head[u];i;i=node[i].next)//head[u]:u点所在的边,node[i].next:u点所在的边的下一个点,就这样遍历下去
{
int d=node[i].v;
if(node[i].val&&dep[d]+1==dep[u])//如果这条边的残量大于0,且没有断层
{
int mi=dfs(d,min(node[i].val,flow-used));
if(mi){
node[i].val-=mi;
node[i^1].val+=mi;
used+=mi;
}
if(used==flow)return used;
}
}
//如果已经到了这里,说明该点出去的所有点都已经流过了
//并且从前面点传过来的流量还有剩余
//则此时,要对该点更改dep
//使得该点与该点出去的点分隔开
--gap[dep[u]];
if(gap[dep[u]]==0)dep[s]=t+1;//出现断层,无法到达t了
dep[u]++;//层++
gap[dep[u]]++;//层数对应个数++
return used;
}
long long ISAP()
{
maxflow=0;
bfs();
while(dep[s]<t) dfs(s,0x3f3f3f3f);//每走一遍增广路,s的层数会加1,如果一直没有出现断层,最多跑n-dep(刚bfs完时s的深度)条增广路共有n个点
return maxflow;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> T;
while (T--) {
cnt = 1;
cin >> n >> m;
s = n + m + 1;
t = n + m + 2;
memset(head + 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);
vector<int> gb(n + 1), hb(m + 1);
int k = gsz[n];
int expect = 0;
gb[n] = k >> 1;
for (int i = n; i > 0; i--) {
int sum = -gb[i];
bool flag = false;
for(int j : g[i]) {
if(gsz[j] & 1) {
gb[j] = (gsz[j] >> 1) + flag;
addedge(j, i, flag ^ 1);
addedge(i, j, flag);
flag ^= 1;
}
else
gb[j] = gsz[j] >> 1;
sum += gb[j];
}
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);
}
}
hb[m] = k >> 1;
for (int i = m; i > 0; i--) {
int sum = hb[i];
bool flag = false;
for(int j : h[i]) {
if(hsz[j] & 1) {
hb[j] = (hsz[j] >> 1) + flag;
addedge(n + j, n + i, flag);
addedge(n + i, n + j, flag ^ 1);
flag ^= 1;
}
else
hb[j] = hsz[j] >> 1;
sum -= hb[j];
}
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);
}
}
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;
}
if (k & 1) {
addedge(n, n + m, 1);
addedge(n + m, n, 0);
}
if (ISAP() != expect) {
cout << "IMPOSSIBLE\n";
continue;
}
for (int i = 1; i <= k; i++)
cout << (node[cid[i]].val ? 'R' : 'B');
cout << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5672kb
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:
RBBR BRB
result:
ok ok (2 test cases)
Test #2:
score: 0
Accepted
time: 19ms
memory: 5692kb
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:
BRRB BBRRB BRBBRR BBR BRBBR BBRBR BBRR BRBR BRBRBRB BRBRBRB BRB BRBRBR BBR BRBRBRB BBRRBR BRBR BBR BRBRB BBR BRBRB BBRRB BRRB BBBRR BRB BRBRB BBRR BRBRBR BBRBRR BRBR BBRRRB BBRBRR BRBBR BBRBRR BRBBRR BBRRBR BRB BRRB RBB BBR BBBRR BRRB BRBRBR BBR BBRBR RBB BRBRBR BRBRBR BRB BRBRBR BRB RBB BRBR BRBRB ...
result:
ok ok (10000 test cases)
Test #3:
score: 0
Accepted
time: 30ms
memory: 5756kb
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:
BRBRRBBBRBBBRRRRRRBRBBBBBBRRR BRBRBBBRBBBRRRRRBBRBBRRR BBBBRBRRBBBBBBRBRBBRBRRRRRRRRRRBBBBBBBBRRBRRBBBRRRRBRRBRRBRBRRBRRRRBBBBBBRRBRBR BBRRRBBRBRBRRRBRBBBBBBRRR RBBBRBRBBRBRBBBRBBRRRBRRBRRBRRRBBRBRRBBRBRRBRRRBBB RRBBRRBBBBBRRBRBBRRBRRRBBRRBBRRBRBBR RBBBBBBBBRBRBBRBBRBRRRRBRRBRRRRBBBRRRR RBRBBRB RRBB...
result:
ok ok (1000 test cases)
Test #4:
score: 0
Accepted
time: 82ms
memory: 7064kb
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:
BBBBBBBRRBBBBRRBBBRRBBRBBBBBRBBBRRBBBBBBBBBBBRBBBBRRBRBBBBRBRBRBBBBBBBBRBRBBRBBRBBBRBBBBBBBRBRRBBBBBBBBBBBBBBBBRBBBBBBBRBBBBRBBRBBBRRRBBBBBBBBBBBRBBBBBRBBBBRBBBBRRBBRBRBBBBBRBBBRBBRBBBBRBRBBBBBRRBBRRBBBBRBBRBRBBBRRBRBBRBBRBBRRRBBRBBBRBRRBRBBBRRRBRRBRRBBRBBBBBRBBRRBBBBRBBBBBBBRBBRBRBRBBBBBBRRRBRBBBBR...
result:
ok ok (10 test cases)
Test #5:
score: 0
Accepted
time: 25ms
memory: 26784kb
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: 0
Accepted
time: 197ms
memory: 26116kb
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 ...
output:
BBBBRBRRRR
result:
ok ok (1 test case)
Test #7:
score: -100
Time Limit Exceeded
input:
1 100000 100000 218 381 317 660 186 296 679 224 357 361 193 231 232 288 310 183 209 206 182 300 400 344 250 440 519 563 203 333 346 543 427 447 245 289 202 386 221 249 256 359 257 370 200 393 263 270 340 191 240 644 489 522 380 453 241 207 345 719 261 336 364 260 211 541 178 215 383 220 886 403 441 ...