Codeforces Round #584 - Dasha Code Championship - Elimination Round F問題 - Koala and Notebook

Source

Codeforces Round #584 - Dasha Code Championship - Elimination Round F問題 (2500pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20190914-1）のコード

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月26日14時57分41秒
Last modified: 2019年09月15日12時54分38秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF584
トップページに戻る

Logged in as: unknown user (not login)