oj.uz

Submission #169588

# Submission time Handle Problem Language Result Execution time Memory
169588 2019-12-21T09:20:21 Z SamAnd Special graph (IZhO13_specialg) C++17
100 / 100
 195 ms 44772 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10872 KB Output is correct
2 Correct 14 ms 11128 KB Output is correct
3 Correct 14 ms 11000 KB Output is correct
4 Correct 15 ms 11000 KB Output is correct
5 Correct 14 ms 11000 KB Output is correct
6 Correct 20 ms 11256 KB Output is correct
7 Correct 21 ms 11256 KB Output is correct
8 Correct 22 ms 11384 KB Output is correct
9 Correct 21 ms 11256 KB Output is correct
10 Correct 22 ms 11384 KB Output is correct
11 Correct 181 ms 44772 KB Output is correct
12 Correct 138 ms 29048 KB Output is correct
13 Correct 166 ms 34776 KB Output is correct
14 Correct 128 ms 26744 KB Output is correct
15 Correct 144 ms 29816 KB Output is correct
16 Correct 141 ms 29224 KB Output is correct
17 Correct 195 ms 40948 KB Output is correct
18 Correct 183 ms 40948 KB Output is correct
19 Correct 186 ms 40820 KB Output is correct
20 Correct 179 ms 44724 KB Output is correct