oj.uz

Submission #364641

# Submission time Handle Problem Language Result Execution time Memory
364641 2021-02-09T15:57:32 Z TruaShamu Regions (IOI09_regions) C++11
95 / 100
 8000 ms 55852 KB 
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define F first
#define S second

using namespace std;

const int N = 200005, K = 25001;
const int INF = 1e9;
const int B = 250;
const int P = N / B + 5;

int n, r, q, p[N], a[N];
int prec[P][K];
vector <int> g[N], has[K];

int id[K], cnt[K];
void dfs(int v, int cnt, int start) {
    cnt += start == a[v];
    if (a[v] != start) prec[id[start]][a[v]] += cnt;
    for (int i : g[v]) {
        dfs(i, cnt, start);
    }
}

int in[N], out[N], T = 0;
vector <int> ins[K];
void dfs(int v) {
    in[v] = ++T;
    ins[a[v]].pb(in[v]);
    for (int i : g[v]) {
        dfs(i);
    }
    out[v] = T;
}

int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> r >> q;
    for (int i = 1; i <= n; i++) {
        if (i == 1) cin >> a[i];
        else cin >> p[i] >> a[i];
    }
    for (int i = 2; i <= n; i++) {
        g[p[i]].pb(i);
    }
    for (int i = 1; i <= n; i++) {
        cnt[a[i]]++, has[a[i]].pb(i);
    }
    int cur = 0;
    for (int i = 1; i <= r; i++) {
        if (cnt[i] > B) {
            id[i] = ++cur;
            dfs(1, 0, i);
        }
    }
    dfs(1);
    while(q--) {
        int p, q; cin >> p >> q;
        if (cnt[p] > B) {
            cout << prec[id[p]][q] << endl;
            continue;
        }
        int res = 0;
        for (int i : has[p]) {
            res += upper_bound(ins[q].begin(), ins[q].end(), out[i]) -
                   lower_bound(ins[q].begin(), ins[q].end(), in[i]);
        }
        cout << res << endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6252 KB Output is correct
2 Correct 5 ms 6252 KB Output is correct
3 Correct 7 ms 6252 KB Output is correct
4 Correct 9 ms 6252 KB Output is correct
5 Correct 11 ms 6252 KB Output is correct
6 Correct 19 ms 6252 KB Output is correct
7 Correct 30 ms 6380 KB Output is correct
8 Correct 35 ms 6380 KB Output is correct
9 Correct 47 ms 6636 KB Output is correct
10 Correct 83 ms 6764 KB Output is correct
11 Correct 141 ms 7148 KB Output is correct
12 Correct 161 ms 7532 KB Output is correct
13 Correct 202 ms 7404 KB Output is correct
14 Correct 321 ms 8044 KB Output is correct
15 Correct 291 ms 9964 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2041 ms 11356 KB Output is correct
2 Correct 1965 ms 10544 KB Output is correct
3 Correct 3529 ms 13156 KB Output is correct
4 Correct 351 ms 8044 KB Output is correct
5 Correct 433 ms 9324 KB Output is correct
6 Correct 661 ms 11244 KB Output is correct
7 Correct 1392 ms 12780 KB Output is correct
8 Correct 1220 ms 20076 KB Output is correct
9 Correct 3447 ms 22760 KB Output is correct
10 Correct 3882 ms 31320 KB Output is correct
11 Execution timed out 8067 ms 55852 KB Time limit exceeded
12 Correct 1878 ms 17772 KB Output is correct
13 Correct 2564 ms 18156 KB Output is correct
14 Correct 3637 ms 19692 KB Output is correct
15 Correct 4113 ms 22468 KB Output is correct
16 Correct 3949 ms 27884 KB Output is correct
17 Correct 4147 ms 28268 KB Output is correct