oj.uz

Submission #733841

# Submission time Handle Problem Language Result Execution time Memory
733841 2023-05-01T11:05:45 Z GrindMachine Regions (IOI09_regions) C++17
35 / 100
 4510 ms 39608 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++;

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

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

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

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

    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 10 ms 18384 KB Output is correct
3 Correct 10 ms 18256 KB Output is correct
4 Correct 11 ms 18256 KB Output is correct
5 Correct 15 ms 18256 KB Output is correct
6 Correct 24 ms 18384 KB Output is correct
7 Correct 33 ms 18304 KB Output is correct
8 Correct 36 ms 18504 KB Output is correct
9 Correct 43 ms 18868 KB Output is correct
10 Correct 63 ms 18780 KB Output is correct
11 Correct 139 ms 18996 KB Output is correct
12 Correct 128 ms 19496 KB Output is correct
13 Correct 207 ms 19076 KB Output is correct
14 Correct 345 ms 19536 KB Output is correct
15 Correct 290 ms 22652 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1594 ms 22372 KB Output isn't correct
2 Incorrect 1930 ms 20948 KB Output isn't correct
3 Incorrect 2529 ms 24328 KB Output isn't correct
4 Correct 279 ms 19712 KB Output is correct
5 Correct 260 ms 21592 KB Output is correct
6 Incorrect 558 ms 22416 KB Output isn't correct
7 Incorrect 1750 ms 22164 KB Output isn't correct
8 Incorrect 1052 ms 31124 KB Output isn't correct
9 Correct 2439 ms 26352 KB Output is correct
10 Incorrect 3926 ms 35892 KB Output isn't correct
11 Correct 4510 ms 25420 KB Output is correct
12 Incorrect 1464 ms 27008 KB Output isn't correct
13 Incorrect 1803 ms 27464 KB Output isn't correct
14 Incorrect 1889 ms 28580 KB Output isn't correct
15 Incorrect 3390 ms 32452 KB Output isn't correct
16 Incorrect 2882 ms 39600 KB Output isn't correct
17 Incorrect 2899 ms 39608 KB Output isn't correct