Submission #961082

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define INF (1e9+1)
//#define INF (1LL<<59)



//verified AOJ GRL_3
#define MAX_V 100000
vector<int> G[MAX_V];   //辺
vector<int> rG[MAX_V];  //逆辺
vector<string> str;

void add_edge(int from, int to){
	G[from].push_back(to);
	rG[to].push_back(from);
}

void dfs(int v, bool used[MAX_V], vector<int> &vs){     //末端から遠いノードから順に、たどり着けるノードをvsに入れていく
	used[v] = true;
	rep(i,G[v].size()){
		if(!used[G[v][i]])dfs(G[v][i],used,vs);
	}
	vs.push_back(v);
}

void rdfs(int v,int k,vector<int> &sccs, vector<int> &cmp, bool used[MAX_V]){   //逆辺を使って末端に近いノードから順にDFS
	used[v] = true;
	sccs.push_back(v);
	cmp[v] = k;
	rep(i,rG[v].size()){
		if(!used[rG[v][i]])rdfs(rG[v][i],k,sccs,cmp,used);
	}
}

int scc(int V, vector< vector<int> > &each_scc, vector<int> &cmp){
	vector<int> vs;
	bool used[MAX_V];
	rep(i,MAX_V)used[i] = false;
	vs.clear();
	rep(v,V){
		if(!used[v]) dfs(v, used, vs);
	}
	
	rep(i,MAX_V) used[i] = false;
	int k=0;
	for(int i=vs.size()-1;i>=0;i--){
		vector<int> sccs;
		if(!used[vs[i]]){
			rdfs(vs[i], k++, sccs, cmp, used);
			each_scc.push_back(sccs);
		}
	}
	return k;
}

vector<int> circle_size;

string nom(string s){
	bool f=false;
	string ret="";
	rep(i,s.size()){
		if(s[i]=='0'){
			if(f)ret+=s[i];
		}else{
			f=true;
			ret+=s[i];
		}
	}
	return ret;
}



void sub(string &s){
	for(int i=(int)s.size()-1;i>=0;i--){
		if(s[i]!='0'){
			s[i]--;
			return;
		}
		else{
			s[i]='9';
		}
	}
}

string f(int n){stringstream ss;ss<<n;return ss.str();}


string modstr(int mod,string t){
	int num=0;
	rep(i,t.size()){
		num*=10;
		num+=t[i]-'0';
		num%=mod;
	}
	return f(num);
}

int dfs(int cur, string t,vector<bool> used){
	if( circle_size[cur]!=1 ) t = modstr(circle_size[cur],t);
	
	if(t[0]=='0')t = nom(t);
	if(t=="") return cur;
	
	int to = G[cur][0];
	used[to]=true;
	sub(t);
	return dfs(to,t,used);
}


int main(){
	assert(modstr(123,"379")=="10");
	int v,a;
	string t;
	cin>>v>>a>>t;
	a--;
	vector<int> b(v);
	rep(i,v)cin>>b[i];
	rep(i,v)b[i]--;
	
	rep(i,b.size()) add_edge(i,b[i]);
	vector<vector<int>> each_scc;  //それぞれの強連結成分のリスト
	vector<int> cmp(MAX_V);        //あるノードが属している強連結成分の番号( 多分each_sccに対応している )
	int k = scc(v,each_scc,cmp);   //強連結成分の個数
	
	circle_size.resize(v);
	rep(i,v){
		circle_size[i] = each_scc[cmp[i]].size();
	}
	
	vector<bool> used(v,false);
	used[a]=true;
	cout<<dfs(a,t,used)+1<<endl;
}

Submission Info

Judge Result