oj.uz

Submission #1097302

# Submission time Handle Problem Language Result Execution time Memory
1097302 2024-10-06T19:09:26 Z DaciejMaciej Regions (IOI09_regions) C++17
57 / 100
 2637 ms 69904 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--;
        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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Runtime error 1 ms 344 KB Execution killed with signal 6
3 Correct 1 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 13 ms 344 KB Output is correct
8 Correct 19 ms 600 KB Output is correct
9 Correct 32 ms 1364 KB Output is correct
10 Correct 50 ms 1112 KB Output is correct
11 Correct 77 ms 1368 KB Output is correct
12 Correct 89 ms 2136 KB Output is correct
13 Correct 127 ms 1880 KB Output is correct
14 Runtime error 21 ms 4944 KB Execution killed with signal 6
15 Runtime error 32 ms 14508 KB Execution killed with signal 6

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 14672 KB Execution killed with signal 6
2 Runtime error 59 ms 11228 KB Execution killed with signal 6
3 Correct 2259 ms 10556 KB Output is correct
4 Correct 194 ms 2648 KB Output is correct
5 Correct 250 ms 5020 KB Output is correct
6 Runtime error 106 ms 12708 KB Execution killed with signal 6
7 Runtime error 125 ms 16384 KB Execution killed with signal 6
8 Correct 936 ms 18800 KB Output is correct
9 Correct 1770 ms 13480 KB Output is correct
10 Correct 2468 ms 32688 KB Output is correct
11 Correct 2637 ms 14388 KB Output is correct
12 Correct 991 ms 15824 KB Output is correct
13 Runtime error 108 ms 33616 KB Execution killed with signal 6
14 Runtime error 295 ms 35920 KB Execution killed with signal 6
15 Runtime error 112 ms 47184 KB Execution killed with signal 6
16 Runtime error 152 ms 69904 KB Execution killed with signal 6
17 Correct 2518 ms 33820 KB Output is correct