Codeforces #578 Div2 F. Graph Traveler

うーん。
https://codeforces.com/contest/1200/problem/F

問題

N頂点2N辺の有向グラフが与えられる。
各頂点最低1個は外向きの辺がある。

各点vには整数値K[v]が設定されている。

頂点番号vと現在値cが与えられたとき、以下の手順でグラフ上を移動した際に何個の点を無限回通るか答えよ。

• vの点の外向きの辺がm個あるとき、c mod m番目の辺に沿って移動。
• 移動先の点v'でcにK[v']を加算する。

解法

mは1～10なので、cの値は実質LCM(1,2,3,4,5,6,7,8,9,10)=2520通りだけ考慮すればよい。
そこで頂点番号と現在値で計2520N通りからなるグラフを考え、先に閉路を検出しておこう。

int N;
int K[1010];
pair<int,int> nex[1010][2520];
int P,Q;

int num[1010][2520];
int vis[1010][2520];


int dfs(int v,int val,vector<int>& V) {
	if(vis[v][val]==2) {
		set<int> S;
		int i;
		for(i=V.size()-1;i>=0;i--) {
			S.insert(V[i]/2520);
			if(V[i]==v*2520+val) break;
		}
		num[v][val]=S.size();
	}
	else if(vis[v][val]==0) {
		vis[v][val]=2;
		V.push_back(v*2520+val);
		num[v][val]=dfs(nex[v][val].first,nex[v][val].second,V);
		V.pop_back();
	}
	vis[v][val]=1;
	return num[v][val];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>K[i];
		K[i]=(K[i]%2520+2520)%2520;
	}
	FOR(i,N) {
		vector<int> E;
		cin>>x;
		E.resize(x);
		FOR(j,x) cin>>E[j];
		FOR(j,2520) {
			nex[i][j].first=E[(j+K[i])%x]-1;
			nex[i][j].second=(j+K[i])%2520;
		}
	}
	FOR(i,N) FOR(j,2520) if(vis[i][j]==0) {
		vector<int> V;
		dfs(i,j,V);
	}
	
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		x--;
		y=(y%2520+2520)%2520;
		cout<<num[x][y]<<endl;
	}
}

まとめ

特に目新しい内容もないしDiv2Fとしてはえらく単純。