Submission #176060

#	Time	Username	Problem	Language	Result	Execution time	Memory
176060		emil_physmath	Special graph (IZhO13_specialg)	C++17	0 / 100	4 ms	632 KiB

specialg

// #define DEBUG
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long llong;

int nei[300001], depth[300001], cycleSize[300001], cycleEnd[300001];
bool used[300001], inCycle[300001], okCycle[300001];

int DFS(int v, int dep = 0)
{
    used[v] = true;
    depth[v] = dep;
    if (!nei[v])
        return 0;
    if (used[nei[v]])
    {
        inCycle[v] = true;
        cycleEnd[v] = v;
        cycleSize[v] = depth[v] - depth[nei[v]] + 1;
        return cycleEnd[v];
    }
    cycleEnd[v] = DFS(nei[v], dep + 1);
    if (cycleEnd[v])
    {
        inCycle[v] = true;
        cycleSize[v] = cycleSize[nei[v]];
        return cycleEnd[v];
    }
    return 0;
}
int par[300001], sz[300001], cyc[300001];
int Root(int v)
{
    // cerr << "v: " << v << endl;
    return par[v] == 0 ? v : par[v] = Root(par[v]);
}
void Union(int u, int v)
{
    u = Root(u); v = Root(v);
    if (u == v)
        return;
    if (sz[u] > sz[v])
        swap(u, v);
    sz[v] += sz[u];
    cyc[v] += cyc[u];
    if (cyc[v] == cycleSize[v] && Root(cycleEnd[v]) == Root(nei[cycleEnd[v]]))
        okCycle[cycleEnd[v]] = true;
    par[u] = v;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    set<int> roots;
    for (int v = 1; v <= n; ++v)
        roots.insert(v);
    for (int v = 1; v <= n; ++v)
    {
        cin >> nei[v];
        roots.erase(nei[v]);
    }
    for (int v: roots)
        DFS(v);
    for (int v = 1; v <= n; ++v)
        if (!used[v])
            DFS(v);
    struct Q
    {
        int type;
        int s, e, v;
    };
    int m;
    cin >> m;
    vector<Q> q(m);
    set<int> notDel;
    for (int i = 1; i <= n; ++i)
        notDel.insert(i);
    for (int i = 0; i < m; ++i)
    {
        cin >> q[i].type;
        if (q[i].type == 1)
        {
            cin >> q[i].v;
            notDel.erase(q[i].v);
        }
        else
            cin >> q[i].s >> q[i].e;
    }
    for (auto x: notDel)
    {
        Q curQ;
        curQ.type = 1;
        curQ.v = x;
        q.push_back(curQ);
    }
    m = q.size();
    reverse(q.begin(), q.end());
    vector<int> ans;
    fill(sz, sz + n + 1, 1);
    for (int i = 1; i <= n; ++i)
        cyc[i] = inCycle[i];
    for (int i = 0; i < q.size(); ++i)
    {
        if (q[i].type == 1)
            Union(q[i].v, nei[q[i].v]);
        else
        {
            int s = q[i].s, e = q[i].e;
            // if (i == 5)
                // cerr << s << ' ' << e << endl;
            if (Root(s) == Root(e))
            {
                if (depth[s] <= depth[e])
                    ans.push_back(depth[e] - depth[s]);
                else if (inCycle[s] && inCycle[e] && cycleEnd[s] == cycleEnd[e] && okCycle[cycleEnd[s]])
                    ans.push_back(cycleSize[cycleEnd[s]] - (depth[s] - depth[e]));
                else
                    ans.push_back(-1);
            }
            else
                ans.push_back(-1);
        }
    }
    reverse(ans.begin(), ans.end());
    for (int x: ans)
        cout << x << ' ';
}

Compilation message (stderr)

specialg.cpp: In function 'int main()':
specialg.cpp:107:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < q.size(); ++i)
                     ~~^~~~~~~~~~

• Subtask 1: 0 / 100