Submission #47525

#	Time	Username	Problem	Language	Result	Execution time	Memory
47525		aome	Special graph (IZhO13_specialg)	C++17	100 / 100	133 ms	34904 KiB

specialg

#include <bits/stdc++.h>
using namespace std;

struct Query {
    int t, x, y;
    Query (int t, int x, int y) : t(t), x(x), y(y) {}
};

const int N = 100005;

int n, m, cnt;
int h[N], p[20][N], nxt[N];
int par[N], deg[N], res[N];
int pos[N], cir[N], sz[N];
bool visit[N], iscir[N];
vector<int> G[N];
vector<Query> query;

void dfs(int u) {
    for (auto v : G[u]) {
        if (v == p[0][u]) continue;
        h[v] = h[u] + 1, dfs(v);
    }
}

void find_cir(int u) {
    pos[u] = ++sz[cnt], cir[u] = cnt;
    if (cir[nxt[u]]) return;
    find_cir(nxt[u]);
}

void pre() {
    for (int i = 1; i <= n; ++i) {
        if (nxt[i]) deg[nxt[i]]++;
    }

    queue<int> qu;
    for (int i = 1; i <= n; ++i) {
        if (!deg[i]) qu.push(i);
    }

    while (qu.size()) {
        int u = qu.front(); qu.pop();
        if (nxt[u]) {
            deg[nxt[u]]--;
            if (!deg[nxt[u]]) {
                qu.push(nxt[u]);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (nxt[i] && !deg[i]) {
            p[0][i] = nxt[i], G[nxt[i]].push_back(i);
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (!p[0][i]) p[0][i] = i, dfs(i);
    }

    for (int i = 1; i <= 17; ++i) {
        for (int j = 1; j <= n; ++j) {
            p[i][j] = p[i - 1][p[i - 1][j]];
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (deg[i] && !cir[i]) ++cnt, find_cir(i);
    }
}

bool check(int u, int v) {
    for (int i = 17; i >= 0; --i) {
        if (h[p[i][u]] >= h[v]) u = p[i][u];
    }
    return u == v;
}

int find(int u) {
    return u == par[u] ? u : par[u] = find(par[u]);
}

void join(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) { iscir[u] = 1; return; }
    par[u] = v;
}

int main() {
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> nxt[i];
    for (int i = 1; i <= n; ++i) par[i] = i;
    pre();

    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int t, x, y;
        cin >> t; x = y = 0;
        if (t == 1) cin >> x, visit[x] = 1;
        else cin >> x >> y;
        query.push_back(Query(t, x, y));
    }

    for (int i = 1; i <= n; ++i) {
        if (!visit[i] && nxt[i]) join(i, nxt[i]);
    }

    for (int i = m - 1; i >= 0; --i) {
        int t = query[i].t, x = query[i].x, y = query[i].y;
        if (t == 1) join(x, nxt[x]);
        else {
            int px = find(x), py = find(y);
            if (px == py) {
                if (check(x, y)) res[i] = h[x] - h[y];
                else {
                    int tmp = p[17][x];
                    if (!cir[tmp] || !cir[px] || cir[tmp] != cir[y]) res[i] = -1;
                    else {
                        res[i] = h[x] + pos[y] - pos[tmp];
                        if (iscir[px]) {
                            if (pos[tmp] > pos[y]) res[i] += sz[cir[y]];
                        }
                        else {
                            if (pos[tmp] < pos[y]) {
                                if (pos[tmp] <= pos[px] && pos[px] < pos[y]) res[i] = -1;
                            }
                            else {
                                if (pos[tmp] <= pos[px] || pos[px] < pos[y]) res[i] = -1;
                                else res[i] += sz[cir[y]];
                            }
                        }
                    }
                }
            }
            else res[i] = -1;
        }
    }

    for (int i = 0; i < m; ++i) {
        if (query[i].t == 2) cout << res[i] << '\n';
    }
}

• Subtask 1: 100 / 100