Codeforces Round #681 (based on VK Cup 2019-2020 - Final) DIV1 C問題/Final B問題 - Graph Transpositions

Source

Codeforces Round #681 (based on VK Cup 2019-2020 - Final) DIV1 C問題 (1500pt)
VK Cup 2019-2020 - Final Round B問題 (1000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20201102-1）のコード

C++に変換後のコードはこちら

//no-unlocked
#define MD 998244353
int N, M, A[2d5], B[2d5];

graph g[2];
int dist[20][2d5];
int q[1d7], qs, qe;

{
  int t, i, j, k;
  ll nres, c;
  Modint res;
  DijkstraHeap<ll> hp;
  rd(N,M,(A--,B--)(M));
  g[0].setDirectEdge(N,M,A,B);
  g[1].setDirectEdge(N,M,B,A);
  
  dimcomp2 dm(N);
  rep(i,20) rep(j,N) dist[i][j] = int_inf;
  dist[0][0] = 0;
  qs = qe = 5d6;
  q[qe++] = 0;
  while(qe > qs){
    dm(q[qs++], t, i);
    rep[g[t%2].edge[i]](k,g[t%2].es[i]){
      if(dist[t][k] != int_inf) continue;
      dist[t][k] = dist[t][i] + 1;
      q[qe++] = dm(t,k);
    }
    if(t+1 < 20 && dist[t+1][i] == int_inf){
      dist[t+1][i] = dist[t][i];
      q[--qs] = dm(t+1, i);
    }
  }

  nres = ll_inf;
  rep(i,20) if(dist[i][N-1] != int_inf) nres <?= dist[i][N-1] + (1LL<<i) - 1;
  if(nres != ll_inf) wt(nres), return 0;

  hp.walloc(2*N);
  hp.init(2*N);
  hp.change(0, 0LL);
  while(hp.size){
    dm(hp.pop(), t, i);
    c = hp.val[dm(t,i)];
    hp.change(dm((t+1)%2,i), c + 1d10);
    rep[g[t%2].edge[i]](k,g[t%2].es[i]) hp.change(dm(t,k), c+1);
  }

  rep(t,2) if(hp.visited[dm(t,N-1)]) nres <?= hp.val[dm(t,N-1)];
  res = Modint(2) ** (nres/1d10) + nres%1d10 - 1;
  wt(res);
}

Current time: 2024年04月25日08時58分16秒
Last modified: 2020年11月03日08時08分19秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF681 CF_DIV1_C
トップページに戻る

Logged in as: unknown user (not login)