Submission #170479

#	Time	Username	Problem	Language	Result	Execution time	Memory
170479		davitmarg	Special graph (IZhO13_specialg)	C++17	0 / 100	9 ms	3388 KiB

specialg

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 100005;

int n, k, q, par[N], T[N], up[N][25], mn[N][25], tin[N], tout[N], timer;
int val[N], used[N], parent[N], d[N];
vector<pair<pair<int, int>, int>> query;
vector<int> g[N], st, t;

void dfs(int v, int p, int start)
{
    parent[v] = start;
    up[v][0] = p;
    mn[v][0] = val[v];
    tin[v] = ++timer;
    for (int i = 1; i <= k; i++)
    {
        up[v][i] = up[up[v][i - 1]][i - 1];
        mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
    }
    for (int i = 0; i < g[v].size(); i++)
    {
        int to = g[v][i];
        if (parent[v] == to)
            continue;
        d[to] = d[v] + 1;
        dfs(to, v, start);
    }
    tout[v] = ++timer;
}

bool upper(int a, int b)
{
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}

int get(int a, int b)
{
    if (a == b)
        return mod;
    assert(upper(a, b));
    int res = mod;
    for (int i = k; i >= 0; i--)
        if (!upper(up[b][i], a))
        {
            res = min(res, mn[b][i]);
            b = up[b][i];
        }
    if (up[b][0] == a)
        res = min(res, mn[b][0]);
    return res;
}

void topsort(int v)
{
    used[v] = 1;
    if (par[v] != 0 && !used[par[v]])
        topsort(par[v]);
    t.PB(v);
    T[v] = n - t.size();
}

int main()
{
    cin >> n;
    while ((1 << k) <= n)
        k++;

    for (int i = 1; i <= n; i++)
        scanf("%d", par + i);

    for (int i = 1; i <= n; i++)
        val[i] = mod;

    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int t, a, b;
        scanf("%d%d", &t, &a);
        if (t == 2)
        {
            scanf("%d", &b);
            query.PB(MP(MP(a, b), i));
        }
        else
            val[a] = i;
    }

    for (int i = 1; i <= n; i++)
        if (!used[i])
            topsort(i);

    reverse(all(t));
    for (int i = 0; i < t.size(); i++)
    {
        int v = t[i];
        if (par[v] == 0 || T[par[v]] < T[v])
            st.PB(v);
    }

    for (int i = 1; i <= n; i++)
        g[par[i]].PB(i);

    for (int i = 0; i < st.size(); i++)
        dfs(st[i], st[i], st[i]);

    for (int i = 0; i < query.size(); i++)
    {
        int a, b, t;
        a = query[i].first.first;
        b = query[i].first.second;
        t = query[i].second;
        if (parent[a] != parent[b])
        {
            printf("-1\n");
            continue;
        }
        if (upper(b, a))
        {
            if (get(b, a) > t)
                printf("%d\n", d[a] - d[b]);
            else
                printf("-1\n");
            continue;
        }
        if (par[parent[a]] && upper(b, par[parent[a]]) && get(b, par[parent[a]]) > t && get(parent[a], a) > t)
        {
            printf("%d\n", d[a] + 1 + d[par[parent[a]]] - d[b]);
            continue;
        }
        printf("-1\n");
    }

    return 0;
}

/*

6
3 3 4 5 6 4
6
2 1 6
2 1 4
2 1 2
1 3
2 1 6
2 1 4


*/

Compilation message (stderr)

specialg.cpp: In function 'void dfs(int, int, int)':
specialg.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[v].size(); i++)
                     ~~^~~~~~~~~~~~~
specialg.cpp: In function 'int main()':
specialg.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < t.size(); i++)
                     ~~^~~~~~~~~~
specialg.cpp:127:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < st.size(); i++)
                     ~~^~~~~~~~~~~
specialg.cpp:130:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < query.size(); i++)
                     ~~^~~~~~~~~~~~~~
specialg.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", par + i);
         ~~~~~^~~~~~~~~~~~~~~
specialg.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &t, &a);
         ~~~~~^~~~~~~~~~~~~~~~
specialg.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b);
             ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 100