Submission #169588

#	Time	Username	Problem	Language	Result	Execution time	Memory
169588		SamAnd	Special graph (IZhO13_specialg)	C++17	100 / 100	195 ms	44772 KiB

specialg

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, INF = 1000000009;
struct ban
{
    int x, y;
    ban()
    {
        x = y = 0;
    }
};

int n, m;
int a[N];
int han[N];
ban q[N];

int c[N];
int pp[N];
int s, f;
bool dfsc(int x)
{
    c[x] = 1;
    int h = a[x];
    if (h)
    {
        if (c[h] == 1)
        {
            s = h;
            f = x;
            c[x] = 2;
            return true;
        }
        else if (c[h] == 0)
        {
            pp[h] = x;
            if (dfsc(h))
            {
                c[x] = 2;
                return true;
            }
        }
    }
    c[x] = 2;
    return false;
}

int k;
vector<int> v[N];
vector<int> vminu[N];
int ch[N], ci[N];

vector<int> b[N];
vector<int> bhan[N];

const int l = 19;
int p[N][l];
int minu[N][l];
int d[N];
int tin[N], tout[N], ti;
void dfs0(int x, int pp, int ph, int xx)
{
    tin[x] = ++ti;
    p[x][0] = pp;
    minu[x][0] = ph;
    for (int i = 1; i < l; ++i)
    {
        p[x][i] = p[p[x][i - 1]][i - 1];
        minu[x][i] = min(minu[x][i - 1], minu[p[x][i - 1]][i - 1]);
    }
    for (int i = 0; i < b[x].size(); ++i)
    {
        int h = b[x][i];
        if (h == xx)
            continue;
        d[h] = d[x] + 1;
        dfs0(h, x, bhan[x][i], xx);
    }
    tout[x] = ti;
}

bool isp(int x, int y)
{
    return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}

int go(int x, int y)
{
    int yminu = INF;
    for (int i = l - 1; i >= 0; --i)
    {
        if (!isp(p[x][i], y))
        {
            yminu = min(yminu, minu[x][i]);
            x = p[x][i];
        }
    }
    yminu = min(yminu, minu[x][0]);
    return yminu;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
    {
        if (!a[i])
            a[i] = i;
    }
    for (int i = 1; i <= n; ++i)
        han[i] = INF;
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i)
    {
        int ty;
        scanf("%d", &ty);
        if (ty == 1)
        {
            scanf("%d", &q[i].x);
            han[q[i].x] = i;
        }
        else
        {
            scanf("%d%d", &q[i].x, &q[i].y);
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!c[i])
        {
            if (dfsc(i))
            {
                ++k;
                for (int i = f; i != s; i = pp[i])
                    v[k].push_back(i);
                v[k].push_back(s);
                reverse(v[k].begin(), v[k].end());
                vminu[k].assign(v[k].size(), INF);
                for (int i = 0; i < v[k].size(); ++i)
                {
                    ch[v[k][i]] = k;
                    ci[v[k][i]] = i;
                    if (i)
                        vminu[k][i] = min(vminu[k][i - 1], han[v[k][i - 1]]);
                }
            }
        }
    }
    /*printf("%d\n", k);
    for (int i = 1; i <= k; ++i)
    {
        for (int j = 0; j < v[i].size(); ++j)
            printf("%d ", v[i][j]);
        printf("\n");
    }*/
    for (int i = 1; i <= n; ++i)
    {
        b[a[i]].push_back(i);
        bhan[a[i]].push_back(han[i]);
    }
    for (int i = 1; i <= k; ++i)
    {
        dfs0(v[i][0], v[i][0], INF, v[i][0]);
    }
    for (int i = 1; i <= m; ++i)
    {
        int x = q[i].x;
        int y = q[i].y;
        if (!y)
            continue;
        if (x == y)
        {
            printf("0\n");
            continue;
        }
        if (isp(y, x))
        {
            if (go(x, y) > i)
            {
                printf("%d\n", d[x] - d[y]);
            }
            else
            {
                printf("-1\n");
            }
            continue;
        }
        if (minu[x][l - 1] > i && ch[y] == ch[p[x][l - 1]])
        {
            if (vminu[ch[y]][ci[y]] > i)
            {
                printf("%d\n", d[x] + ci[y]);
            }
            else
                printf("-1\n");
            continue;
        }
        printf("-1\n");
    }
    return 0;
}

Compilation message (stderr)

specialg.cpp: In function 'void dfs0(int, int, int, int)':
specialg.cpp:71:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < b[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
specialg.cpp: In function 'int main()':
specialg.cpp:142:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int i = 0; i < v[k].size(); ++i)
                                 ~~^~~~~~~~~~~~~
specialg.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
specialg.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
specialg.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
specialg.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ty);
         ~~~~~^~~~~~~~~~~
specialg.cpp:122:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &q[i].x);
             ~~~~~^~~~~~~~~~~~~~~
specialg.cpp:127:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &q[i].x, &q[i].y);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100