Codeforces Round #383 (Div. 2) C. Arpa's loud Owf and Mehrdad's evil plan

問題

Problem - C - Codeforces

考察

色々と試して見ると、まず「輪っかにならない長さ2以上の数列」ができるとアウトになることがわかります。
また、輪っかの長さが偶数ならその半分の長さで済み、奇数ならその長さが必要なこともわかります。

1つの問題中に複数の輪っかが同時に出るので、それらを全て満たす長さ(それぞれ必要な長さのlcm)を取れば良いです。

輪っかになっているかどうかはdfsを2周すると求めることができます。
また、輪っかの長さはUnionFindを使うと簡単に求まります(dfsでまとめてやってもOKだと思います)。

コード

struct UnionFind {
    vector<int> data;

    UnionFind(int size) : data(size, -1) {}

    bool unionSet(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }

    bool findSet(int x, int y) {
        return root(x) == root(y);
    }

    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }

    int size(int x) {
        return -data[root(x)];
    }
};

vi d(110, -1);
vvi graph;

void dfs(int v) {
    if (d[v] == -1) {
        d[v] = 0;
    } else if (d[v] == 0) {
        d[v] = 1;
    } else if (d[v] == 1) {
        return;
    }

    tr(it, graph[v]) {
        dfs(*it);
    }
}

ll gcd(ll a, ll b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll m, ll n) {
    if ((0 == m) || (0 == n))
        return 0;

    return ((m / gcd(m, n)) * n);
}

int main() {
    int n;
    cin >> n;

    graph.resize(n);
    d.resize(n);

    UnionFind uf(n);
    rep(i, n) {
        int t;
        cin >> t;
        t--;
        uf.unionSet(i, t);
        graph[i].push_back(t);
    }

    rep(i, n) {
        fill(all(d), -1);
        dfs(i);
        rep(j, n) {
            if (d[j] == 0) {
                cout << -1 << endl;
                return 0;
            }
        }
    }

    ll ans = 1;
    rep(i, n) {
        int t = uf.size(i);
        if (t == 1 || t == 2) {
        } else {
            if (t % 2 == 0)
                ans = lcm(ans, t / 2);
            else
                ans = lcm(ans, t);
        }
    }

    cout << ans << endl;

    return 0;
}

感想

罠は無いですがタイトルが長いです。