oj.uz

Submission #731553

# Submission time Handle Problem Language Result Execution time Memory
731553 2023-04-27T14:26:58 Z Desh03 Regions (IOI09_regions) C++17
25 / 100
 8000 ms 25444 KB 
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> r, g;
vector<int> euler, in, out, fr, c;
int t, cnt, b;
const int block = 447;

void dfs(int u) {
    in[u] = t++;
    euler.push_back(u);
    for (int v : g[u])
        dfs(v);
    out[u] = t - 1;
}

void add(int x) {
    cnt += c[euler[x]] == b;
}

void remove(int x) {
    cnt -= c[euler[x]] == b;
}

int main() {
    int n, rr, qq;
    cin >> n >> rr >> qq;
    g.resize(n), r.resize(rr), in.resize(n), out.resize(n), fr.resize(rr), c.resize(n);
    int x, h;
    cin >> h;
    h--;
    r[h].push_back(0);
    c[0] = h;
    for (int i = 1; i < n; i++) {
        cin >> x >> h;
        x--, h--;
        r[h].push_back(i);
        g[x].push_back(i);
        c[i] = h;
    }
    dfs(0);
    for (int i = 0; i < rr; i++) {
        sort(r[i].begin(), r[i].end(), [](const int &a, const int &b) {
             int a1 = in[a] / block, b1 = in[b] / block;
             return a1 == b1 ? out[a] < out[b] : a1 < b1;
        });
    }
    while (qq--) {
        int a, ans = 0;
        cin >> a >> b;
        a--, b--, cnt = 0;
        int lb, rb;
        if (r[a].size()) lb = in[r[a][0]] + 1, rb = lb - 1;
        for (int u : r[a]) {
            int l_ = in[u] + 1, r_ = out[u];
            while (lb > l_) add(--lb);
            while (rb < r_) add(++rb);
            while (lb < l_) remove(lb++);
            while (rb > r_) remove(rb--);
            ans += cnt;
        }
        cout << ans << endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 3 ms 208 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 9 ms 336 KB Output is correct
6 Correct 23 ms 336 KB Output is correct
7 Correct 37 ms 336 KB Output is correct
8 Correct 58 ms 464 KB Output is correct
9 Correct 120 ms 848 KB Output is correct
10 Correct 268 ms 1104 KB Output is correct
11 Correct 750 ms 1488 KB Output is correct
12 Correct 1339 ms 2256 KB Output is correct
13 Correct 922 ms 1928 KB Output is correct
14 Correct 1781 ms 2640 KB Output is correct
15 Correct 1826 ms 5404 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8020 ms 6896 KB Time limit exceeded
2 Execution timed out 8039 ms 5760 KB Time limit exceeded
3 Execution timed out 8025 ms 8900 KB Time limit exceeded
4 Correct 2935 ms 2776 KB Output is correct
5 Correct 3348 ms 4704 KB Output is correct
6 Execution timed out 8013 ms 4540 KB Time limit exceeded
7 Execution timed out 8084 ms 6216 KB Time limit exceeded
8 Execution timed out 8012 ms 11632 KB Time limit exceeded
9 Execution timed out 8096 ms 13488 KB Time limit exceeded
10 Execution timed out 8029 ms 18620 KB Time limit exceeded
11 Execution timed out 8002 ms 14372 KB Time limit exceeded
12 Execution timed out 8073 ms 15720 KB Time limit exceeded
13 Execution timed out 8048 ms 16008 KB Time limit exceeded
14 Execution timed out 8103 ms 15924 KB Time limit exceeded
15 Execution timed out 8100 ms 20188 KB Time limit exceeded
16 Execution timed out 8055 ms 25444 KB Time limit exceeded
17 Execution timed out 8082 ms 24196 KB Time limit exceeded