WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #175 Div2 B "Find Marble"

問題

http://codeforces.com/contest/285/problem/B

Codeforces Round #175 Div2 - くじらにっき++で訳してくれています。

自分は未だに理解できていない部分が・・・

考えた事

一回シャッフルして次のようになったとする

1 2 3 4
↓
2 3 1 4

後はこれをs->tまで何回でいけるのかたどっていく。
例えばs=2 t=1であれば
2->3 3->1となって2回シャッフルすればよい。
もしtに着く前にsに戻ってしまったら永久にたどり着けない。(s=4 t=2など)

シャッフル後はどんな位置になるのかは
何回か紙で試したところ、入力のp1, p2, ..., pnとまったく同じになる。

ソースコード

int after[100001];

int main() {
    int n, s, t;
    cin >> n >> s >> t;
    
    // s == tであればシャッフルの必要なし
    if( s == t ){
        cout << 0 << endl;
        return 0;
    }
    // シャッフル後の配置入力
    for( int i = 1; i <= n; i++ ){
        in >> after[i];
    }
    
    // たどっていく
    int p = s;
    int res = 0;
    while( p != t ){
        p = after[p];
        res++;
        if( p == s ) break;
    }

    if( p == s ) res = -1;

    cout << res << endl;
}