oj.uz

Submission #516016

# Submission time Handle Problem Language Result Execution time Memory
516016 2022-01-20T09:57:14 Z apostoldaniel854 Regions (IOI09_regions) C++14
100 / 100
 3848 ms 35656 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"

const int RAD = 500;
const int MAX_N = 2e5;

int H[1 + MAX_N];
vector <int> gr[1 + MAX_N];
vector <int> order[1 + MAX_N];
vector <int> v[1 + MAX_N];
int L[1 + MAX_N], R[1 + MAX_N];
int id[1 + MAX_N];
int sol[RAD][1 + MAX_N];
int freq[1 + MAX_N];


void dfs(int node, int cnt, int color) {
    if (H[node] == color)
        cnt++;
    else
        sol[id[color]][H[node]] += cnt;
    for (int son : gr[node])
        dfs(son, cnt, color);
}
int mom;
void prec(int node) {
    L[node] = ++mom;
    order[H[node]].push_back(mom);
    for (int son : gr[node])
        prec(son);
    R[node] = mom;
}
int get(int lb, int rb, int color) {
    return upper_bound(order[color].begin(), order[color].end(), rb) - lower_bound(order[color].begin(), order[color].end(), lb);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int N, RR, Q;
    cin >> N >> RR >> Q;
    for (int i = 1; i <= N; i++) {
        if (i == 1)
            cin >> H[i];
        else {
            int par;
            cin >> par >> H[i];
            gr[par].push_back(i);
        }
    }
    for (int i = 1; i <= N; i++) {
        freq[H[i]]++;
        v[H[i]].push_back(i);
    }
    int nr = 0;
    for (int i = 1; i <= RR; i++) {
        if (freq[i] > RAD) {
            id[i] = ++nr;
            dfs(1, 0, i);
        }
    }
    prec(1);
    while (Q--) {
        int a, b;
        cin >> a >> b;
        if (freq[a] > RAD)
            cout << sol[id[a]][b] << endl;
        else {
            int ans = 0;
            for (int node : v[a])
                ans += get(L[node], R[node], b);
            cout << ans << endl;
        }
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14408 KB Output is correct
2 Correct 7 ms 14344 KB Output is correct
3 Correct 9 ms 14336 KB Output is correct
4 Correct 8 ms 14408 KB Output is correct
5 Correct 13 ms 14408 KB Output is correct
6 Correct 25 ms 14408 KB Output is correct
7 Correct 35 ms 14408 KB Output is correct
8 Correct 39 ms 14536 KB Output is correct
9 Correct 44 ms 14792 KB Output is correct
10 Correct 89 ms 14920 KB Output is correct
11 Correct 72 ms 15248 KB Output is correct
12 Correct 152 ms 15620 KB Output is correct
13 Correct 207 ms 15432 KB Output is correct
14 Correct 285 ms 16036 KB Output is correct
15 Correct 261 ms 17924 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1699 ms 19128 KB Output is correct
2 Correct 2091 ms 17980 KB Output is correct
3 Correct 2856 ms 20928 KB Output is correct
4 Correct 158 ms 16072 KB Output is correct
5 Correct 382 ms 17320 KB Output is correct
6 Correct 1285 ms 17224 KB Output is correct
7 Correct 1666 ms 18232 KB Output is correct
8 Correct 1095 ms 22288 KB Output is correct
9 Correct 2334 ms 23616 KB Output is correct
10 Correct 3848 ms 27456 KB Output is correct
11 Correct 3691 ms 23768 KB Output is correct
12 Correct 1296 ms 25388 KB Output is correct
13 Correct 1867 ms 25468 KB Output is correct
14 Correct 2424 ms 27104 KB Output is correct
15 Correct 2958 ms 29820 KB Output is correct
16 Correct 2750 ms 35012 KB Output is correct
17 Correct 2844 ms 35656 KB Output is correct