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
Submission Time |
|
Task |
D - へんてこ辞書 |
User |
Yazaten |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
2872 Byte |
Status |
AC |
Exec Time |
153 ms |
Memory |
55568 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
50 / 50 |
50 / 50 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample_01.txt, subtask0_sample_03.txt |
Subtask1 |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask0_sample_01.txt, subtask0_sample_03.txt |
All |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask0_sample_01.txt, subtask0_sample_03.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt, subtask1_sample_02.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_0.txt |
AC |
117 ms |
22028 KB |
subtask0_1.txt |
AC |
86 ms |
15896 KB |
subtask0_2.txt |
AC |
95 ms |
18428 KB |
subtask0_3.txt |
AC |
80 ms |
14864 KB |
subtask0_4.txt |
AC |
102 ms |
17868 KB |
subtask0_5.txt |
AC |
86 ms |
15780 KB |
subtask0_6.txt |
AC |
76 ms |
15092 KB |
subtask0_7.txt |
AC |
92 ms |
16752 KB |
subtask0_8.txt |
AC |
80 ms |
16904 KB |
subtask0_9.txt |
AC |
101 ms |
17248 KB |
subtask0_sample_01.txt |
AC |
31 ms |
6168 KB |
subtask0_sample_03.txt |
AC |
28 ms |
6216 KB |
subtask1_0.txt |
AC |
92 ms |
21124 KB |
subtask1_1.txt |
AC |
153 ms |
55568 KB |
subtask1_10.txt |
AC |
115 ms |
22600 KB |
subtask1_11.txt |
AC |
30 ms |
6212 KB |
subtask1_2.txt |
AC |
104 ms |
31372 KB |
subtask1_3.txt |
AC |
86 ms |
22560 KB |
subtask1_4.txt |
AC |
80 ms |
15368 KB |
subtask1_5.txt |
AC |
138 ms |
43232 KB |
subtask1_6.txt |
AC |
95 ms |
25124 KB |
subtask1_7.txt |
AC |
71 ms |
12952 KB |
subtask1_8.txt |
AC |
118 ms |
25928 KB |
subtask1_9.txt |
AC |
114 ms |
23600 KB |
subtask1_sample_02.txt |
AC |
30 ms |
6212 KB |