oj.uz

Submission #170482

# Submission time Handle Problem Language Result Execution time Memory
170482 2019-12-25T11:51:58 Z davitmarg Special graph (IZhO13_specialg) C++17
100 / 100
 242 ms 37328 KB 
/*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 && val[parent[a]] > t)
        {
            printf("%d\n", d[a] + 1 + d[par[parent[a]]] - d[b]);
            continue;
        }
        printf("-1\n");
    }

    return 0;
}

/*

2 
2 0
3



*/

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3064 KB Output is correct
2 Correct 7 ms 3320 KB Output is correct
3 Correct 4 ms 3192 KB Output is correct
4 Correct 8 ms 3256 KB Output is correct
5 Correct 6 ms 3192 KB Output is correct
6 Correct 15 ms 3696 KB Output is correct
7 Correct 16 ms 3780 KB Output is correct
8 Correct 16 ms 3828 KB Output is correct
9 Correct 16 ms 3828 KB Output is correct
10 Correct 16 ms 3956 KB Output is correct
11 Correct 206 ms 37224 KB Output is correct
12 Correct 135 ms 23016 KB Output is correct
13 Correct 168 ms 29164 KB Output is correct
14 Correct 127 ms 20716 KB Output is correct
15 Correct 139 ms 24012 KB Output is correct
16 Correct 129 ms 23400 KB Output is correct
17 Correct 186 ms 35464 KB Output is correct
18 Correct 206 ms 35696 KB Output is correct
19 Correct 242 ms 35432 KB Output is correct
20 Correct 214 ms 37328 KB Output is correct