ABC 030 D - へんてこ辞書 ( Ad hoc )

D: へんてこ辞書 - AtCoder Beginner Contest 030 | AtCoder
Find the length before getting into the cycle, and the length of the cycle. Then get K in mod len_cycle, O( N ).

const int MAXN = 1e5 + 2;

int N, A;
string K;
int B[ MAXN ];

void solve(){
    cin >> N >> A; --A;
    cin >> K;
    for( int i = 0; i < N; ++i )
        cin >> B[ i ], --B[ i ];

    vi step2node, node2step( N, -1 );
    int len_before_c = -1;
    int len_cycle = -1;
    for( int u = A; ; u = B[ u ] ){
        if( node2step[ u ] != -1 ){
            len_before_c = node2step[ u ];
            len_cycle = step2node.size() - len_before_c;
            break;
        }
        node2step[ u ] = step2node.size();
        step2node.push_back( u );
    }

    if( K.size() < 7 and stoi( K ) < len_before_c ){
        cout << step2node[ stoi( K ) ] + 1 << "\n";
        return;
    }

    int k = 0;
    for( int i = 0; i < K.size(); ++i )
        ( k = k * 10 + K[ i ] - '0' ) %= len_cycle;

    k -= len_before_c; k %= len_cycle; k += len_cycle; k %= len_cycle;
    cout << step2node[ len_before_c + k ] + 1 << "\n";
}