oj.uz

Submission #1097299

# Submission time Handle Problem Language Result Execution time Memory
1097299 2024-10-06T19:01:48 Z DaciejMaciej Regions (IOI09_regions) C++17
0 / 100
 3525 ms 113960 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(r);
    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));
        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);
            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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Runtime error 1 ms 344 KB Execution killed with signal 11
3 Runtime error 1 ms 344 KB Execution killed with signal 11
4 Runtime error 1 ms 344 KB Execution killed with signal 11
5 Runtime error 1 ms 600 KB Execution killed with signal 11
6 Runtime error 1 ms 760 KB Execution killed with signal 11
7 Runtime error 2 ms 600 KB Execution killed with signal 11
8 Runtime error 1 ms 600 KB Execution killed with signal 11
9 Runtime error 2 ms 1112 KB Execution killed with signal 11
10 Runtime error 5 ms 3160 KB Execution killed with signal 11
11 Runtime error 10 ms 4440 KB Execution killed with signal 11
12 Runtime error 12 ms 6232 KB Execution killed with signal 11
13 Runtime error 90 ms 2956 KB Execution killed with signal 6
14 Runtime error 15 ms 8536 KB Execution killed with signal 11
15 Runtime error 38 ms 23216 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 41668 KB Execution killed with signal 11
2 Runtime error 698 ms 7460 KB Execution killed with signal 6
3 Runtime error 80 ms 49736 KB Execution killed with signal 11
4 Runtime error 18 ms 9048 KB Execution killed with signal 11
5 Runtime error 294 ms 9428 KB Execution killed with signal 6
6 Runtime error 44 ms 29320 KB Execution killed with signal 11
7 Runtime error 67 ms 38632 KB Execution killed with signal 11
8 Runtime error 77 ms 58276 KB Execution killed with signal 11
9 Runtime error 959 ms 16592 KB Execution killed with signal 6
10 Runtime error 3099 ms 39404 KB Execution killed with signal 6
11 Runtime error 1439 ms 17612 KB Execution killed with signal 11
12 Runtime error 148 ms 105720 KB Execution killed with signal 11
13 Runtime error 141 ms 103736 KB Execution killed with signal 11
14 Runtime error 213 ms 113036 KB Execution killed with signal 11
15 Runtime error 2199 ms 33200 KB Execution killed with signal 6
16 Runtime error 3525 ms 70604 KB Execution killed with signal 6
17 Runtime error 160 ms 113960 KB Execution killed with signal 11