oj.uz

Submission #733846

# Submission time Handle Problem Language Result Execution time Memory
733846 2023-05-01T11:09:52 Z GrindMachine Regions (IOI09_regions) C++17
100 / 100
 5115 ms 39604 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
const int B = 455;

int n, r, q;
vector<int> adj[N];
vector<int> a(N);
vector<int> id(N, -1);
vector<int> curr_cnt(N);
vector<vector<int>> ans_heavy;
int siz;
vector<int> tin(N), tout(N);
int timer = 1;

void dfs(int u, int p) {
    tin[u] = timer++;
    ll c = a[u];

    if (id[c] != -1) {
        curr_cnt[id[c]]++;
    }

    rep(id, siz) {
        ans_heavy[id][c] += curr_cnt[id];
    }

    trav(v, adj[u]) {
        if (v == p) conts;
        dfs(v, u);
    }

    if (id[c] != -1) {
        curr_cnt[id[c]]--;
    }

    tout[u] = timer++;
}

vector<int> nodes[N];
vector<int> tins[N];

void solve(int test_case)
{
    cin >> n >> r >> q;
    cin >> a[1];

    for (int i = 2; i <= n; ++i) {
        int p, h; cin >> p >> h;
        adj[p].pb(i);
        a[i] = h;
    }

    vector<int> cnt(r + 5);
    rep1(i, n) cnt[a[i]]++;

    siz = 0;

    rep1(c, r) {
        if (cnt[c] > B) {
            id[c] = siz++;
        }
    }

    ans_heavy = vector<vector<int>>(siz, vector<int>(r + 5));
    dfs(1, -1);

    rep1(i, n) {
        nodes[a[i]].pb(i);
        tins[a[i]].pb(tin[i]);
    }

    rep1(c, r) {
        sort(all(tins[c]));
    }

    while (q--) {
        int c1, c2; cin >> c1 >> c2;
        int ans = 0;

        if (id[c1] != -1) {
            ans = ans_heavy[id[c1]][c2];
        }
        else {
            auto &ti = tins[c2];
            trav(u, nodes[c1]) {
                int l = tin[u], r = tout[u];
                int cnt = upper_bound(all(ti), r) - lower_bound(all(ti), l);
                ans += cnt;
            }
        }

        cout << ans << endl;
    }
}

int main()
{
    fastio;

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

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18256 KB Output is correct
2 Correct 9 ms 18256 KB Output is correct
3 Correct 14 ms 18272 KB Output is correct
4 Correct 11 ms 18256 KB Output is correct
5 Correct 15 ms 18256 KB Output is correct
6 Correct 28 ms 18420 KB Output is correct
7 Correct 33 ms 18384 KB Output is correct
8 Correct 43 ms 18440 KB Output is correct
9 Correct 67 ms 18792 KB Output is correct
10 Correct 97 ms 18752 KB Output is correct
11 Correct 160 ms 19000 KB Output is correct
12 Correct 148 ms 19396 KB Output is correct
13 Correct 180 ms 19076 KB Output is correct
14 Correct 333 ms 19608 KB Output is correct
15 Correct 284 ms 22644 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2043 ms 22364 KB Output is correct
2 Correct 1889 ms 20944 KB Output is correct
3 Correct 2973 ms 24328 KB Output is correct
4 Correct 299 ms 19708 KB Output is correct
5 Correct 392 ms 21592 KB Output is correct
6 Correct 536 ms 22420 KB Output is correct
7 Correct 1371 ms 22160 KB Output is correct
8 Correct 879 ms 31120 KB Output is correct
9 Correct 2259 ms 26356 KB Output is correct
10 Correct 3874 ms 35892 KB Output is correct
11 Correct 5115 ms 25424 KB Output is correct
12 Correct 1570 ms 27012 KB Output is correct
13 Correct 2312 ms 27464 KB Output is correct
14 Correct 2279 ms 28576 KB Output is correct
15 Correct 3504 ms 32440 KB Output is correct
16 Correct 3237 ms 39596 KB Output is correct
17 Correct 2916 ms 39604 KB Output is correct