oj.uz

Submission #731709

# Submission time Handle Problem Language Result Execution time Memory
731709 2023-04-27T20:33:32 Z Desh03 Regions (IOI09_regions) C++17
35 / 100
 8000 ms 28016 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;
    vector<unordered_map<short int, int>> mp2(rr);
    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;
        if (mp2[a].find(b) != mp2[a].end()) {
            cout << mp2[a][b] << '\n';
            continue;
        }
        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;
        mp2[a][b] = ans;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 5 ms 324 KB Output is correct
5 Correct 7 ms 348 KB Output is correct
6 Correct 21 ms 468 KB Output is correct
7 Correct 33 ms 476 KB Output is correct
8 Correct 46 ms 524 KB Output is correct
9 Correct 79 ms 1144 KB Output is correct
10 Correct 242 ms 1548 KB Output is correct
11 Correct 621 ms 1884 KB Output is correct
12 Correct 1127 ms 2708 KB Output is correct
13 Correct 868 ms 2412 KB Output is correct
14 Correct 1426 ms 3088 KB Output is correct
15 Correct 1587 ms 6000 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8058 ms 7340 KB Time limit exceeded
2 Execution timed out 8093 ms 6320 KB Time limit exceeded
3 Execution timed out 8045 ms 9588 KB Time limit exceeded
4 Correct 2897 ms 4172 KB Output is correct
5 Correct 3293 ms 6408 KB Output is correct
6 Correct 5980 ms 6968 KB Output is correct
7 Correct 4729 ms 7732 KB Output is correct
8 Execution timed out 8020 ms 13184 KB Time limit exceeded
9 Execution timed out 8007 ms 14528 KB Time limit exceeded
10 Execution timed out 8060 ms 20392 KB Time limit exceeded
11 Execution timed out 8063 ms 16124 KB Time limit exceeded
12 Execution timed out 8039 ms 16676 KB Time limit exceeded
13 Execution timed out 8010 ms 17036 KB Time limit exceeded
14 Execution timed out 8007 ms 17020 KB Time limit exceeded
15 Execution timed out 8071 ms 21800 KB Time limit exceeded
16 Execution timed out 8048 ms 28016 KB Time limit exceeded
17 Execution timed out 8016 ms 25856 KB Time limit exceeded