QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#316432#8130. Yet Another Balanced Coloring Problemucup-team134#TL 0ms14776kbC++174.2kb2024-01-27 20:46:552024-01-27 20:46:55

Judging History

你现在查看的是最新测评结果

  • [2024-03-18 02:37:14]
  • hack成功,自动添加数据
  • (/hack/577)
  • [2024-01-27 20:46:55]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:14776kb
  • [2024-01-27 20:46:55]
  • 提交

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
...

result: