oj.uz

Submission #516011

# Submission time Handle Problem Language Result Execution time Memory
516011 2022-01-20T09:51:35 Z apostoldaniel854 Regions (IOI09_regions) C++14
0 / 100
 399 ms 35552 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] << "\n";
        else {
            int ans = 0;
            for (int node : v[a])
                ans += get(L[node], R[node], b);
            cout << ans << "\n";
        }
    }
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6 ms 14280 KB Time limit exceeded (wall clock)
2 Execution timed out 8 ms 14408 KB Time limit exceeded (wall clock)
3 Execution timed out 7 ms 14408 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 14408 KB Time limit exceeded (wall clock)
5 Execution timed out 7 ms 14388 KB Time limit exceeded (wall clock)
6 Execution timed out 7 ms 14396 KB Time limit exceeded (wall clock)
7 Execution timed out 7 ms 14408 KB Time limit exceeded (wall clock)
8 Execution timed out 7 ms 14408 KB Time limit exceeded (wall clock)
9 Execution timed out 8 ms 14792 KB Time limit exceeded (wall clock)
10 Execution timed out 10 ms 14920 KB Time limit exceeded (wall clock)
11 Execution timed out 14 ms 15176 KB Time limit exceeded (wall clock)
12 Execution timed out 12 ms 15548 KB Time limit exceeded (wall clock)
13 Execution timed out 12 ms 15424 KB Time limit exceeded (wall clock)
14 Execution timed out 16 ms 15956 KB Time limit exceeded (wall clock)
15 Execution timed out 17 ms 17860 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 40 ms 19068 KB Time limit exceeded (wall clock)
2 Execution timed out 61 ms 17884 KB Time limit exceeded (wall clock)
3 Execution timed out 45 ms 20796 KB Time limit exceeded (wall clock)
4 Execution timed out 15 ms 16072 KB Time limit exceeded (wall clock)
5 Execution timed out 19 ms 17220 KB Time limit exceeded (wall clock)
6 Execution timed out 22 ms 17220 KB Time limit exceeded (wall clock)
7 Execution timed out 32 ms 18244 KB Time limit exceeded (wall clock)
8 Execution timed out 36 ms 22204 KB Time limit exceeded (wall clock)
9 Execution timed out 55 ms 23496 KB Time limit exceeded (wall clock)
10 Execution timed out 55 ms 27456 KB Time limit exceeded (wall clock)
11 Execution timed out 71 ms 23740 KB Time limit exceeded (wall clock)
12 Execution timed out 116 ms 25252 KB Time limit exceeded (wall clock)
13 Execution timed out 114 ms 25404 KB Time limit exceeded (wall clock)
14 Execution timed out 399 ms 27004 KB Time limit exceeded (wall clock)
15 Execution timed out 112 ms 29772 KB Time limit exceeded (wall clock)
16 Execution timed out 73 ms 34988 KB Time limit exceeded (wall clock)
17 Execution timed out 127 ms 35552 KB Time limit exceeded (wall clock)