Submission #227450

#	Time	Username	Problem	Language	Result	Execution time	Memory
227450		emil_physmath	Special graph (IZhO13_specialg)	C++14	100 / 100	118 ms	40008 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;

vector<int> nei[2 * maxN];
int depth[2 * maxN], tin[2 * maxN], tout[2 * maxN], par[2 * maxN];

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()
{
    int 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;
    }
    int stn = n;
    vector<int> used(stn), col(stn, -1);
    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 (to == -1)
                {
                    par[j] = -1;
                    break;
                }
                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);
}
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: 100 / 100