Submission #227402

#	Time	Username	Problem	Language	Result	Execution time	Memory
227402		emil_physmath	Special graph (IZhO13_specialg)	C++17	0 / 100	7 ms	5120 KiB

specialg

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
using llong = long long;
const int maxN = 100'000;
const int inf = 1000'000'000;

int unraw[maxN][2];
vector<int> nxt;

namespace
{
    vector<int> nei[2 * maxN];
    int depth[2 * maxN], tin[2 * maxN], tout[2 * maxN], par[2 * maxN];
    int n;
    void DFS(int v, int par)
    {
        static int tm = 0;
        tin[v] = tm++;
        depth[v] = (par == -1 ? 0 : depth[par] + 1);
        for (int to: nei[v])
            if (to != par)
                DFS(to, v);
        tout[v] = tm;
    }
    inline bool Upper(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
    int root[2 * maxN], sz[2 * maxN];
    void Init()
    {
        n = nxt.size();
        for (int i = 0; i < 2 * n; ++i)
        {
            par[i] = -1;
            root[i] = i;
            sz[i] = 1;
        }
        for (int i = 0; i < n; ++i)
        {
            unraw[i][0] = i;
            unraw[i][1] = -1;
        }
        vector<int> used(n), col(n, -1);
        int stn = n;
        for (int i = 0; i < stn; ++i)
        {
            if (used[i]) continue;
            int j = i;
            int cyc = -1;
            while (true)
            {
                if (used[j] == 0)
                {
                    ++used[j];
                    col[j] = i;
                    int to = nxt[j];
                    if (col[to] != i)
                    {
                        par[j] = to;
                        nei[to].push_back(j);
                        j = to;
                    }
                    else
                    {
                        cyc = j;
                        break;
                    }
                }
                else
                    break;
            }
            if (cyc != -1)
            {
                int rawj = cyc, j = cyc;
                while (true)
                {
                    int rawto = nxt[rawj];
                    if (used[rawto] == 2)
                        break;
                    ++used[rawto];
                    int to = n++;
                    unraw[rawto][1] = to;
                    par[j] = to;
                    nei[to].push_back(j);
                    rawj = rawto;
                    j = to;
                }
            }
        }
        vector<bool> isRoot(n, false);
        for (int i = 0; i < n; ++i)
            if (par[i] == -1)
                isRoot[i] = true;
        for (int i = 0; i < n; ++i)
            if (isRoot[i])
                DFS(i, -1);
        exit(0);
    }
    int Root(int v)
    {
        return (root[v] == v ? v : root[v] = Root(root[v]));
    }
    void Union(int u, int v)
    {
#ifdef MANSON
        cerr << "Union(" << u << ", " << v << ")\n";
#endif
        u = Root(u); v = Root(v);
        if (u == v) return;
        if (sz[u] > sz[v]) swap(u, v);
        root[u] = v;
        sz[v] += sz[u];
    }
    void Add(int v)
    {
#ifdef MANSON
        cerr << "v: " << v << ", par: " << par[v] << '\n';
#endif
        if (par[v] == -1) return;
        Union(v, par[v]);
    }
    int Dist(int u, int v)
    {
        swap(u, v);
        if (u == 4 && v == 2)
            cerr << "";
        if (!Upper(u, v) || Root(u) != Root(v))
            return inf;
        return depth[v] - depth[u];
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    nxt.resize(n);
    vector<bool> isdel(n, true);
    for (int i = 0; i < n; ++i)
    {
        cin >> nxt[i];
        if (nxt[i])
            isdel[i] = false;
        --nxt[i];
    }
    Init();
    int qnum;
    cin >> qnum;
    vector<vector<int>> qs(qnum);
    for (vector<int>& q: qs)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            q.resize(1);
            cin >> q[0]; --q[0];
            isdel[q[0]] = true;
        }
        else
        {
            q.resize(2);
            cin >> q[0] >> q[1]; --q[0]; --q[1];
        }
    }
    for (int i = 0; i < n; ++i)
        if (!isdel[i])
            qs.push_back({i});
    reverse(qs.begin(), qs.end());
    for (vector<int>& q: qs)
    {
        int type = q.size();
        if (type == 1)
        {
            int raw = q[0];
            for (int i = 0; i < 2; ++i)
                if (unraw[raw][i] != -1)
                    Add(unraw[raw][i]);
        }
        else
        {
            int rawu = q[0], rawv = q[1];
            vector<int> us = {unraw[rawu][0], unraw[rawu][1]};
            vector<int> vs = {unraw[rawv][0], unraw[rawv][1]};
            int ans = inf;
            for (int u: us)
                if (u != -1)
                    for (int v: vs)
                        if (v != -1)
                            ans = min(ans, Dist(u, v));
            if (ans == inf)
                q.push_back(-1);
            else
                q.push_back(ans);
        }
    }
    reverse(qs.begin(), qs.end());
    for (auto& q: qs)
        if (q.size() == 3)
            cout << q.back() << '\n';
}

• Subtask 1: 0 / 100