Codeforces Round #584 - Dasha Code Championship - Elimination Round F問題 (2500pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, M, X[1d5], Y[1d5];
int nn, mm, A[2d6], B[2d6], C[2d6];
wgraph<int> g;
vector<int> con[2d6];
mint res[2d6];
int aa[2d6], cc[2d6], es;
int q[2d6], qs, qe;
int vis[2d6];
{
int i, j, k, d[10], ds, p, pv, s;
mint now;
rd(N,M,(X--,Y--)(M));
nn = N;
rep(i,M){
k = i + 1;
ds = 0;
while(k) d[ds++] = k % 10, k /= 10;
for(k = ds-1; k>=0; k--){
A[mm] = if[k==ds-1, X[i], nn-1];
B[mm] = if[k==0, Y[i], nn++];
C[mm++] = d[k];
}
for(k = ds-1; k>=0; k--){
A[mm] = if[k==ds-1, Y[i], nn-1];
B[mm] = if[k==0, X[i], nn++];
C[mm++] = d[k];
}
}
g.setDirectEdge(nn, mm, A, B, C);
vis[0] = 1;
q[qe++] = 0;
while(qs < qe){
i = q[qs++];
now = res[i];
es = 0;
con[i].push_back(i);
rep(j,con[i].size()){
s = con[i][j];
rep(k,g.es[s]){
aa[es] = g.edge[s][k];
cc[es++] = g.cost[s][k];
}
}
sortA(es, cc, aa);
pv = -1;
rep(i,es){
k = aa[i];
if(vis[k]) continue;
vis[k] = 1;
res[k] = 10 now + cc[i];
if(pv != cc[i]){
p = k;
pv = cc[i];
q[qe++] = k;
} else {
con[p].push_back(k);
}
}
}
rep(i,1,N) wt(res[i]);
}
Current time: 2024年04月18日06時51分08秒
Last modified: 2019年09月15日12時54分38秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF584
トップページに戻る
Logged in as: unknown user (not login)