QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#316434#8130. Yet Another Balanced Coloring Problemucup-team134#TL 672ms47152kbC++144.4kb2024-01-27 20:47:542024-01-27 20:47:55

Judging History

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

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

answer

#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#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 bfs(){

    queue<int>q;
    for(int i=source;i<=sink;i++){
        level[i]=0;
    }
    level[source]=1;
    q.push(source);
    while(q.size()){
        int x=q.front();
        q.pop();
        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.push(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));
        for(int i=source;i<=sink;i++)start[i]=0;
        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);

        for(int i=0;i<=n+m+1;i++){
            reverse(vect[i].begin(),vect[i].end());
        }

        ///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: 4ms
memory: 17532kb

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
RBR

result:

ok ok (2 test cases)

Test #2:

score: 0
Accepted
time: 24ms
memory: 17420kb

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:

RRBB
RBRBR
RBRRBB
RRB
RBRRB
RBRRB
BBRR
RBRB
RRRRBBB
RRRRBBB
RBR
RBRRBB
RRB
RBRBRRB
RRRBBB
BRRB
RRB
RRRBB
RRB
BRRBR
RBBRR
RBBR
RRRBB
RRB
RRBBR
RRBB
RBRBBR
RRRBBB
RBRB
BRBRRB
RRBRBB
RRRBB
RRRBBB
RRBRBB
RRBBRB
RBR
RRBB
BRR
RRB
RRRBB
RBBR
RRRBBB
RBR
RBBRR
BRR
RRRBBB
RRBBRB
RRB
RRRBBB
RBR
BRR
RRBB
RBRRB
...

result:

ok ok (10000 test cases)

Test #3:

score: 0
Accepted
time: 43ms
memory: 17872kb

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:

BBBRBRRBBBRBRBRBRRRRBBRRRRBBR
RBBBRBBBRRRRRBRRRBBRRBBB
BRRBBRRRRRRRRBRRRRRRRBRBRRRBBBRRRBBRRRRBBBBBBBBBBRRRRBBBRBBBRRBBBRBBBRRBBBRRBBB
BBBRBBRRBRRBBBRRBBRRRRRRB
RRBBRRRBRRRRBRBBBRRBBRBBBRBRRRRBBBRBRBRRRRBBBRBBBB
RRBBRBRBBBRRRRRRRBRBBBRRRRBRBBBRBBBB
RRBRRRBRRRRBRBBRBBRRRBBRBBRBBBBRRBBBRB
BRBRRBR
BBRR...

result:

ok ok (1000 test cases)

Test #4:

score: 0
Accepted
time: 377ms
memory: 19036kb

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:

RBBRRBRBRBBRBBRBRRRBRBRRBRBRBRRBRRRRRRBRRRBRBBBBRRRRBRRRBBBBBRBBRRRRRBRBRBBBRBRBBRRRBRBRRBRRBBRRRBBRBRBRRRRRRRBRBRRRRBRRBRRBBRBRRRRRRBBRRBBBRRRRRRRRBRBRRRRRRRBBRRBRRBRRBRBBRBBBBBRBBBRBRRRBBRBBRRRBRBRRRRRRRRRRRRBBBRRRRRBRBBRRRRRBBRRBRRRRRRBRRRRBRRRBRBRRRBRRBRBRRRBRRRBBBBRRRRRRBRBRBBRRBRRBRBBRRRRRRRRB...

result:

ok ok (10 test cases)

Test #5:

score: 0
Accepted
time: 33ms
memory: 47152kb

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:

R

result:

ok ok (1 test case)

Test #6:

score: 0
Accepted
time: 71ms
memory: 39584kb

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:

RRRRBRBBBB

result:

ok ok (1 test case)

Test #7:

score: 0
Accepted
time: 672ms
memory: 37544kb

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

output:

RRBBBBBBRBRBRBRRRRBRBBRBRRBBBBRBRRBBBBRBBRRBRBRRRRRRBRBRBBBRRRRBRBRBBRRRBBRBBBRBRRRBRRBRRRRRRBBBBBBBBRRRRBBRRRRBBRRRBBRRBRRBBBRRBBBRRRBBRBBBBRRBRBRRRBRRRBBRBBBBRRBBBRRBBBRRBBBR

result:

ok ok (1 test case)

Test #8:

score: -100
Time Limit Exceeded

input:

1
100000 100000
1421 2788 1423 1160 1112 1488 1236 5948 1163 1757 1410 2312 1361 2923 1593 1342 1999 1293 1081 2501 1942 2294 1893 1059 1610 1844 1256 1287 3866 2443 1668 2351 2721 1191 1618 1058 2556 1182 4821 1303 1528 2149 1564 1294 2339 1490 2179 3047 1645 1178 1536 3950 1275 8455 1068 2870 2234...

output:

RRBRBRBRBRRBRBBRBBBBRRBRRBRBBRBBBBRBRBBRBRBBRRRBBRBBBBBBRBBBRBRRBBRBBBRBRBBRBBBRRBRBRBRBRRBBBRRRRBRRRBRRRRBBBBBBBBRRBRRRBBRRBBBRRRRRRBRRBBRRRRBBBRBBRRRBBRRRRRRRRBBRBBRBBBBRBBBBRRRRRRBBRRBBBBRRBRBRBBRBBBRBRBBRRRBRRBRBRRRRBBRBBRRBBRBBRBBRBRBRBBRRBRRRBBBRBRBRRBBBBRBRRRRBRRBRBRRBBBBBRBRBRRBBRBBBRBRRRBBB...

result: