結果

問題 No.482 あなたの名は
コンテスト
ユーザー @abcde
提出日時 2019-05-25 17:50:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 1,681 bytes
コンパイル時間 1,661 ms
コンパイル使用メモリ 171,148 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-17 15:05:54
合計ジャッジ時間 3,593 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL io[200001];
LL oi[200001];

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// 操作パターンを幅優先探索する.
// ※bfsの動作確認用.
// @param c: 探索地点のインデックス.
// @param o: 操作回数.
// @param o: 探索回数 を 返却.
LL bfs(LL c, LL o){
    
    // 1. 終了条件確認.
    LL ret = o;
    if(io[c] == c) return ret;
    
    // 2. 空のキュー.
    queue<LL> q;
    
    // 3. 訪問済みフラグ設定.
    // -> 特に設定しない.
    // io[c] = c;
    
    // 4. 探索地点 c をキュー q に追加.
    q.push(c);
    while(!q.empty()){
        // 5. キューから取り出す.
        LL v = q.front();
        q.pop();
        
        // 6. 取り出した要素を処理.
        // 未訪問(io[v] != v) であれば, 以下の条件にしたがって, 訪問済みを設定.
        // cout << "io[" << v << "]=" << io[v] << " oi[" << v << "]=" << oi[v] << " ret=" << ret << endl;
        if(io[v] != v) q.push(oi[v]), io[oi[v]] = io[v], io[v] = v, ret++;
    }
    
    // 7. 探索回数 を 返却.
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    LL N, K;
    cin >> N >> K;
    for(LL i = 1; i < N + 1; i++){
        LL d;
        cin >> d;
        io[i] = d, oi[d] = i;
    }
    
    // 2. K回の操作で戻せるか？
    LL count = 0;
    for(LL i = 1; i < N + 1; i++) count += bfs(i, 0);
    
    // 3. 判定.
    string ans = "NO";
    LL diff = K - count;
    if(diff >= 0 && diff % 2 == 0) ans = "YES";
    
    // 4. 後処理.
    cout << ans << endl;
    return 0;
    
}
0