省略
省略
C++に変換後のコードはこちら
int N, M, D[1d5], A[2d5], B[2d5], ind[2d5];
char S[1d5+2];
int C[2d5];
int fg[1d5];
char rev[256];
{
int i, j, k, x;
wgraph<int> g;
LHeap<int> hp;
rev['W'] = 'B';
rev['B'] = 'W';
rd(N,M,(D(N)),(A--,B--)(M));
rep(i,M) ind[i] = i;
g.setEdge(N,M,A,B,ind);
hp.walloc(M);
hp.init(M);
rep(i,M) hp.change(i, int_inf);
rep(i,M) if(D[A[i]] == D[B[i]]) hp.change(i, D[A[i]]);
while(hp.size){
k = hp.pop();
if(hp.val[k]==int_inf) wt(-1), return 0;
if(S[A[k]] == 0 && S[B[k]] == 0) S[A[k]] = 'W';
if(S[A[k]] == 0) S[A[k]] = rev[S[B[k]]];
if(S[B[k]] == 0) S[B[k]] = rev[S[A[k]]];
C[k] = hp.val[k];
rep(loop,2){
i = if[loop==0, A[k], B[k]];
if(fg[i]++) continue;
rep(j,g.es[i]){
x = g.edge[i][j];
if(S[x]==0 && D[x] >= D[i]) hp.change(g.cost[i][j], D[x]);
}
}
}
wtLn(S,C(M));
}
Current time: 2024年04月26日16時18分25秒
Last modified: 2020年01月19日04時39分26秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る
Logged in as: unknown user (not login)