QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#316432 | #8130. Yet Another Balanced Coloring Problem | ucup-team134# | TL | 0ms | 14776kb | C++17 | 4.2kb | 2024-01-27 20:46:55 | 2024-01-27 20:46:55 |
Judging History
answer
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
using namespace std;
typedef pair<int,int> pii;
const int mod=998244353;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
const int maxn=2e5+10;
vector<int>rez_edges;
vector<int>g[maxn],vect[maxn];
struct edge{
int u,v,flow,cap;
};
vector<edge>e;
int incnt[maxn],outcnt[maxn],pos[maxn],sz[maxn],n,m;
int sink,source;
int level[maxn],start[maxn];
void add_edge(int x,int y,int cap){
if(cap==0)return;
vect[x].pb(e.size());
e.pb({x,y,0,cap});
vect[y].pb(e.size());
e.pb({y,x,cap,cap});
/// printf("%d %d | %d\n",x,y,cap);
}
void go(int x){
int child=0;
sz[x]=0;
incnt[x]=0;
outcnt[x]=0;
for(int i=0;i<g[x].size();i++){
int id=g[x][i];
go(id);
child++;
sz[x]+=sz[id];
if(x<=n){
if(sz[id]%2)add_edge(x,id,1);
outcnt[x]+=sz[id]/2;
incnt[id]+=sz[id]/2;
}
else{
if(sz[id]%2)add_edge(id,x,1);
outcnt[id]+=sz[id]/2;
incnt[x]+=sz[id]/2;
}
}
if(child==0){
if(x<=n)rez_edges.pb(e.size());
if(x<=n)add_edge(x,x+n,1);
sz[x]=1;
}
}
int q[maxn];
int bfs(){
memset(level,0,sizeof(level));
level[source]=1;
int tr=0,l=0;
q[tr++]=source;
while(l!=tr){
int x=q[l++];
for(int i=0;i<vect[x].size();i++){
int id=vect[x][i];
if(e[id].flow>=e[id].cap || level[e[id].v])continue;
level[e[id].v]=level[x]+1;
q[tr++]=e[id].v;
}
}
return level[sink];
}
int send_flow(int x,int flow){
if(x==sink)return flow;
for(;start[x]<vect[x].size();start[x]++){
int id=vect[x][start[x]];
if(e[id].flow<e[id].cap && level[x]+1==level[e[id].v]){
int tmpf=send_flow(e[id].v,min(flow,e[id].cap-e[id].flow));
if(tmpf){
e[id].flow+=tmpf;
e[id^1].flow-=tmpf;
return tmpf;
}
}
}
return 0;
}
ll calc_flow(){
ll ret=0;
while(bfs()){
memset(start,0,sizeof(start));
ll pom;
while((pom=send_flow(source,1e9)))ret+=pom;
}
return ret;
}
int main(){
///freopen("test.txt","r",stdin);
int t;
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
e.clear();
rez_edges.clear();
n++;
m++;
for(int i=0;i<=n+m+1;i++){
g[i].clear();
vect[i].clear();
}
for(int i=1;i<n-1;i++){
int a;
scanf("%d",&a);
g[a].pb(i);
}
for(int i=1;i<m-1;i++){
int a;
scanf("%d",&a);
g[a+n].pb(i+n);
}
g[n].pb(n-1);
g[n+m].pb(n+m-1);
source=0;
sink=n+m+1;
go(n);
go(m+n);
ll sum=0;
for(int i=1;i<=n+m;i++){
int pom=min(incnt[i],outcnt[i]);
incnt[i]-=pom;
outcnt[i]-=pom;
add_edge(source,i,incnt[i]);
add_edge(i,sink,outcnt[i]);
sum+=incnt[i];
}
add_edge(m+n,n,1e9);
///printf("%lld SUM\n",sum);
ll pom=calc_flow();
if(pom!=sum){
printf("IMPOSSIBLE\n");
continue;
}
for(int i=0;i<rez_edges.size();i++){
int id=rez_edges[i];
int v=e[id].u;
pos[v]=e[id].flow;
}
for(int i=1;i<=rez_edges.size();i++){
if(pos[i]==0)printf("R");
else printf("B");
}
printf("\n");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 14776kb
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 BRR
result:
ok ok (2 test cases)
Test #2:
score: -100
Time Limit Exceeded
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:
RBBR BBRRR BRBBRR RRB RBRBR RBBRR BBRR RBBR BBBRRRR BRBBRRR RBR BRBBRR RBR BRBRBRR BBRRBR BRRB BRR BRRRB RRB BRRBR RBBRR RBBR BRBRR RBR BBRRR BBRR BBRRRB RBBBRR BRBR BBBRRR BBRBRR BRBRR BBBRRR BBBRRR BRBRBR BRR BBRR BRR RRB BRBRR BBRR RBBRRB RRB RBBRR BRR BBBRRR BRRBBR RBR RBBBRR RBR BRR BRBR BRBRR ...