oj.uz

Submission #1097303

# Submission time Handle Problem Language Result Execution time Memory
1097303 2024-10-06T19:12:21 Z DaciejMaciej Regions (IOI09_regions) C++17
100 / 100
 3018 ms 34688 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;

template <class T>

using VV = vector<vector<T>>;

using VI = vector<int>;
using VVI = vector<vector<int>>;

using VL = vector<long long>;
using VVL = vector<vector<long long>>;

using VC = vector<char>;
using VVC = vector<vector<char>>;

using VB = vector<bool>;
using VVB = vector<vector<bool>>;

using VD = vector<double>;
using VVD = vector<vector<double>>;

using PII = pair<int, int>;
using PLL = pair<long long, long long>;
using PIL = pair<int, long long>;
using PLI = pair<long long, int>;

using VPII = vector<pair<int, int>>;
using VPLL = vector<pair<long long, long long>>;

#define LINE '\n'
#define SPACE ' '
#define PB push_back
#define FOR(i, a, b) for (int i = (a); i < (int(b)); i++)
#define FORE(i, a, b) for (int i = (a); i <= (int)((b)); i++)
#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()
#define sq(a) ((a) * (a))
#define sz(x) ((int)x.size())

#define fastio()                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(nullptr);                 \
    cout.tie(nullptr)
#define debug(x) cerr << #x << " = " << x << endl;

// zero indexed
template <class T>
struct SegTree
{
    const T def = 0;
    int n;
    vector<T> seg;

    SegTree(int _size) : n(_size), seg(2 * _size, def) {}

    inline T merge(T a, T b)
    {
        return max(a, b);
    }

    void update(int pos, T val)
    {
        for (seg[pos += n] = val; pos /= 2;)
        {
            seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1]);
        }
    }

    T query(int l, int r) // get [l, r]
    {
        T a = def, b = def;
        for (l += n, r += n + 1; l < r; l /= 2, r /= 2)
        {
            if (l % 2)
                a = merge(a, seg[l++]);
            if (r % 2)
                b = merge(b, seg[--r]);
        }
        return merge(a, b);
    }
};

template <class T>
struct BIT
{
    int size;
    vector<T> bit;
    vector<T> arr;

    BIT(int _size) : size(_size), bit(_size + 1), arr(_size) {}

    void set(int pos, T val)
    {
        add(pos, val - arr[pos]);
    }
    void add(int pos, T val)
    {
        arr[pos] += val;

        for (pos++; pos <= size; pos += pos & -pos)
        {
            bit[pos] += val;
        }
    }
    T query(int pos)
    {
        T res = 0;
        for (pos++; pos > 0; pos -= pos & -pos)
        {
            res += bit[pos];
        }
        return res;
    }
};

const ll MOD = 1e9 + 7;

template <class T>
inline void maxi(T &a, T b)
{
    a = max(a, b);
}

template <class T>
inline void mini(T &a, T b)
{
    a = min(a, b);
}

template <class T>
inline void addi(T &a, T b)
{
    a = (a + b) % MOD;
}

template <class T>
inline void subi(T &a, T b)
{
    a = (a - b + MOD) % MOD;
}

template <class T>
inline T add(T a, T b)
{
    return (a + b) % MOD;
}

template <class T>
inline T sub(T a, T b)
{
    return (a - b + MOD) % MOD;
}

template <class T>
inline T mul(T a, T b)
{
    return ((a % MOD) * (b % MOD)) % MOD;
}

constexpr ll binpow(ll a, ll b, ll mod)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }

    return res;
}

const int INF = 1e9;

const int MAX_N = 1e5 + 3;

void solve()
{
    int n, r, q;
    cin >> n >> r >> q;
    VI region(n);
    VV<int> g(n);
    cin >> region[0];
    region[0]--;
    FOR(i, 1, n)
    {
        int p, h;
        cin >> p >> h;
        p--, h--;
        g[p].PB(i);
        region[i] = h;
    }

    /*
    tin - in time
    tout - out time
    rtin - rtin[tin[u]] = u
    rg - for each region list of tin vecs
    */
    VI tin(n), tout(n), rtin(n);
    VV<int> rg(r);
    int t = 0;
    function<void(int)> dfs = [&](int c) -> void
    {
        tin[c] = t++;
        rtin[tin[c]] = c;
        rg[region[c]].PB(tin[c]);
        for (auto v : g[c])
        {
            dfs(v);
        }
        tout[c] = t;
    };
    dfs(0);

    const int BS = sqrt(n);
    VV<int> pre;   // pre[id][reg] = ans for query a, b
    VI rid(r, -1); // compress regions ids
    int id = 0;

    function<void(int, int, int)> dfs2 = [&](int c, int pr, int p_size) -> void
    {
        if (region[c] == pr)
        {
            p_size++;
        }
        pre[rid[pr]][region[c]] += p_size;
        for (auto v : g[c])
            dfs2(v, pr, p_size);
    };

    FOR(i, 0, r)
    {
        if (sz(rg[i]) < BS)
            continue;
        rid[i] = id++;
        pre.PB(VI(r, 0));
        dfs2(0, i, 0);
    }

    FOR(i, 0, q)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (rid[a] != -1)
        {
            cout << pre[rid[a]][b] << LINE;
        }
        else
        {
            int rs = 0;
            for (auto v : rg[a])
            { // v is the in time for region a
                rs += lower_bound(ALL(rg[b]), tout[rtin[v]]) -
                      lower_bound(ALL(rg[b]), tin[rtin[v]]);
            }
            cout << rs << LINE;
        }
    }
}

int main()
{
    // fastio();

    int t = 1;
    // cin >> t;

    while (t--)
        solve();
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 4 ms 344 KB Output is correct
6 Correct 10 ms 344 KB Output is correct
7 Correct 18 ms 344 KB Output is correct
8 Correct 18 ms 600 KB Output is correct
9 Correct 28 ms 1112 KB Output is correct
10 Correct 49 ms 1112 KB Output is correct
11 Correct 76 ms 1368 KB Output is correct
12 Correct 100 ms 2132 KB Output is correct
13 Correct 121 ms 1880 KB Output is correct
14 Correct 177 ms 2648 KB Output is correct
15 Correct 209 ms 7320 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1461 ms 7448 KB Output is correct
2 Correct 1725 ms 5808 KB Output is correct
3 Correct 2379 ms 10552 KB Output is correct
4 Correct 204 ms 2648 KB Output is correct
5 Correct 281 ms 5036 KB Output is correct
6 Correct 437 ms 6520 KB Output is correct
7 Correct 956 ms 8256 KB Output is correct
8 Correct 926 ms 18800 KB Output is correct
9 Correct 1835 ms 13480 KB Output is correct
10 Correct 2591 ms 32676 KB Output is correct
11 Correct 3018 ms 14396 KB Output is correct
12 Correct 1108 ms 15832 KB Output is correct
13 Correct 1539 ms 16772 KB Output is correct
14 Correct 1882 ms 17888 KB Output is correct
15 Correct 2780 ms 23504 KB Output is correct
16 Correct 2805 ms 34688 KB Output is correct
17 Correct 2500 ms 33820 KB Output is correct