Codeforces Round #393 (Div. 1) (8VC Venture Cup 2017 - Final Round Div. 1 Edition): A. Pavel and barbecue

,

http://codeforces.com/contest/759/problem/A

problem

バーベキューをしている。 串が$n$本あり、$i$番目の串は$y = i$の位置に$x$軸と平行に右向きで置いてある。 置換$p \in \mathfrak{S}_n$と配列$b : n \to 2$が与えられる。 毎秒ごとに串をその位置$y$により$p$に従って入れかえ$b$に従って反転する。 十分大きな有限秒後に全ての串について「任意の位置に任意の向きで一度以上存在したことがある」を満たすように$p, b$を修正するとき、その修正に必要な要素数の最小値を答えよ。

solution

全体がひとつの有向閉路になるように$p$を修正する。 $b_i = 1$な$i$が奇数個になるよう$p$を修正する。$O(n)$。

note

  • 某合宿 day1 no1 div1 A
  • 問題文が難しい 1

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using namespace std;

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> p(n);
    REP (i, n) {
        scanf("%d", &p[i]);
        -- p[i];
    }
    vector<bool> b(n);
    REP (i, n) {
        int b_i; scanf("%d", &b_i);
        b[i] = b_i;
    }

    // solve
    vector<bool> used(n);
    function<void (int)> go = [&](int i) {
        used[i] = true;
        if (not used[p[i]]) {
            go(p[i]);
        }
    };
    int cycles = 0;
    REP (i, n) {
        if (not used[i]) {
            ++ cycles;
            go(i);
        }
    }
    int sum_b = accumulate(ALL(b), 0);
    int result = (cycles == 1 ? 0 : cycles) + (sum_b % 2 == 0);

    // output
    printf("%d\n", result);
    return 0;
}