oj.uz

Submission #733861

# Submission time Handle Problem Language Result Execution time Memory
733861 2023-05-01T11:18:34 Z GrindMachine Regions (IOI09_regions) C++17
100 / 100
 3100 ms 91272 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 = 155;

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 12 ms 18260 KB Output is correct
4 Correct 13 ms 18284 KB Output is correct
5 Correct 17 ms 18280 KB Output is correct
6 Correct 25 ms 18384 KB Output is correct
7 Correct 44 ms 18384 KB Output is correct
8 Correct 45 ms 18440 KB Output is correct
9 Correct 44 ms 18872 KB Output is correct
10 Correct 65 ms 18776 KB Output is correct
11 Correct 132 ms 19004 KB Output is correct
12 Correct 144 ms 19528 KB Output is correct
13 Correct 199 ms 19076 KB Output is correct
14 Correct 249 ms 19656 KB Output is correct
15 Correct 195 ms 22912 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 22516 KB Output is correct
2 Correct 782 ms 21084 KB Output is correct
3 Correct 1104 ms 24600 KB Output is correct
4 Correct 197 ms 20256 KB Output is correct
5 Correct 378 ms 21592 KB Output is correct
6 Correct 561 ms 22412 KB Output is correct
7 Correct 790 ms 24588 KB Output is correct
8 Correct 1051 ms 31116 KB Output is correct
9 Correct 2206 ms 39224 KB Output is correct
10 Correct 2846 ms 90916 KB Output is correct
11 Correct 3100 ms 84172 KB Output is correct
12 Correct 1940 ms 64616 KB Output is correct
13 Correct 2089 ms 65060 KB Output is correct
14 Correct 2280 ms 67852 KB Output is correct
15 Correct 3021 ms 91272 KB Output is correct
16 Correct 2952 ms 88596 KB Output is correct
17 Correct 2904 ms 78764 KB Output is correct