Codeforces Round #578 DIV2 F問題 - Graph Traveler

Source

Codeforces Round #578 DIV2 F問題 (2500pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20190820-1）のコード

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

//no-unlocked
#define MD 2520
int N, M, K[1000], A[10000], B[10000], Q, X, Y;
graph g;

int dp[1000][MD];
int vis[1000][MD];

int vn[1000], vns;

{
  int i, j, k, x, y, res;

  rd(N,K(N));
  rep(i,N){
    rd(k);
    rep(k){
      rd(j--);
      A[M] = i;
      B[M++] = j;
    }
  }
  g.setDirectEdge(N,M,A,B);

  rep(i,N) K[i] %%= MD;

  rd(Q);
  rep(Q){
    rd(X--,Y);
    Y %%= MD;

    if(dp[X][Y]==0){
      x = X;
      y = Y;
      while(vis[x][y]==0){
        vis[x][y] = 1;
        y = (y + K[x]) % MD;
        x = g.edge[x][y%g.es[x]];
      }

      if(dp[x][y]==0){
        res = 0;
        vns++;
        while(vis[x][y]==1){
          vis[x][y] = 2;
          if(vn[x] != vns) vn[x] = vns, res++;
          y = (y + K[x]) % MD;
          x = g.edge[x][y%g.es[x]];
        }
      } else {
        res = dp[x][y];
      }

      x = X;
      y = Y;
      while(dp[x][y]==0){
        dp[x][y] = res;
        y = (y + K[x]) % MD;
        x = g.edge[x][y%g.es[x]];
      }
    }

    wt(dp[X][Y]);
  }
}

Current time: 2024年04月19日18時37分10秒
Last modified: 2019年08月22日00時40分09秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF578 CF_Div2_F
トップページに戻る

Logged in as: unknown user (not login)