Submission #1097302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097302		DaciejMaciej	Regions (IOI09_regions)	C++17	57 / 100	2637 ms	69904 KiB

regions

#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--;
        assert(p < n);
        assert(i < n);

        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
    {
        assert(c < n);
        assert(tin[c] < n);
        assert(region[c] < r);

        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
    {
        assert(sz(pre) > rid[pr]);
        assert(sz(pre[rid[pr]]) == r);
        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));
        dfs2(0, i, 0);
    }

    FOR(i, 0, q)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (rid[a] != -1)
        {
            assert(sz(rg[a]) >= BS);
            assert(sz(pre[rid[b]]) > b);
            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]), v);
            }
            cout << rs << LINE;
        }
    }
}

int main()
{
    // fastio();

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

    while (t--)
        solve();
}

• Subtask 1: 12 / 15
• Subtask 2: 45 / 85