oj.uz

Submission #733870

# Submission time Handle Problem Language Result Execution time Memory
733870 2023-05-01T11:24:48 Z GrindMachine Regions (IOI09_regions) C++17
100 / 100
 4911 ms 119664 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 = 305;

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_heavy1, ans_heavy2, pref_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]]++;
        pref_heavy[id[c]][tin[u]]++;
    }

    rep(id, siz) {
        ans_heavy1[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 - 1;
}

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_heavy1 = vector<vector<int>>(siz, vector<int>(r + 5));
    ans_heavy2 = vector<vector<int>>(r + 5, vector<int>(siz));
    pref_heavy = vector<vector<int>>(siz, vector<int>(n + 5));

    dfs(1, -1);

    rep(c, siz) {
        rep1(i, n) {
            pref_heavy[c][i] += pref_heavy[c][i - 1];
        }
    }

    rep1(i, n) {
        ll l = tin[i], r = tout[i];
        rep(c, siz) {
            ll cnt = pref_heavy[c][r] - pref_heavy[c][l - 1];
            ans_heavy2[a[i]][c] += cnt;
        }
    }

    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_heavy1[id[c1]][c2];
        }
        else if (id[c2] != -1) {
            ans = ans_heavy2[c1][id[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 12 ms 18300 KB Output is correct
4 Correct 13 ms 18256 KB Output is correct
5 Correct 14 ms 18256 KB Output is correct
6 Correct 27 ms 18384 KB Output is correct
7 Correct 33 ms 18384 KB Output is correct
8 Correct 23 ms 18452 KB Output is correct
9 Correct 61 ms 18896 KB Output is correct
10 Correct 78 ms 18796 KB Output is correct
11 Correct 108 ms 19028 KB Output is correct
12 Correct 147 ms 19504 KB Output is correct
13 Correct 200 ms 19084 KB Output is correct
14 Correct 307 ms 19608 KB Output is correct
15 Correct 272 ms 22696 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 944 ms 28932 KB Output is correct
2 Correct 1570 ms 24972 KB Output is correct
3 Correct 2237 ms 27872 KB Output is correct
4 Correct 290 ms 19800 KB Output is correct
5 Correct 386 ms 21712 KB Output is correct
6 Correct 452 ms 36616 KB Output is correct
7 Correct 701 ms 39092 KB Output is correct
8 Correct 974 ms 74764 KB Output is correct
9 Correct 1814 ms 52400 KB Output is correct
10 Correct 2323 ms 119664 KB Output is correct
11 Correct 4911 ms 97956 KB Output is correct
12 Correct 1505 ms 29376 KB Output is correct
13 Correct 2138 ms 29824 KB Output is correct
14 Correct 2216 ms 48216 KB Output is correct
15 Correct 3264 ms 35404 KB Output is correct
16 Correct 2882 ms 42548 KB Output is correct
17 Correct 2813 ms 60336 KB Output is correct