oj.uz

Submission #731616

# Submission time Handle Problem Language Result Execution time Memory
731616 2023-04-27T16:49:02 Z Desh03 Regions (IOI09_regions) C++17
34 / 100
 8000 ms 131072 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;
    map<int, map<int, int>> mp;
    map<pair<int, int>, int> mp2;
    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.find({a, b}) != mp2.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]) {
            if (mp[u].find(b) != mp[u].end()) cnt += mp[u][b];
            else {
                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--);
                mp[u][b] = cnt;
                ans += cnt;
            }
        }
        cout << ans << endl;
        mp2[{a, b}] = ans;
    }
}

Subtask #1
14.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 336 KB Output is correct
4 Correct 6 ms 336 KB Output is correct
5 Correct 12 ms 720 KB Output is correct
6 Correct 25 ms 820 KB Output is correct
7 Correct 54 ms 1988 KB Output is correct
8 Correct 63 ms 2376 KB Output is correct
9 Correct 139 ms 5508 KB Output is correct
10 Correct 440 ms 11128 KB Output is correct
11 Correct 934 ms 27876 KB Output is correct
12 Correct 1713 ms 29040 KB Output is correct
13 Correct 1580 ms 48608 KB Output is correct
14 Correct 3086 ms 93948 KB Output is correct
15 Runtime error 2961 ms 131072 KB Execution killed with signal 9

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 3099 ms 131072 KB Execution killed with signal 9
2 Runtime error 2296 ms 131072 KB Execution killed with signal 9
3 Runtime error 2669 ms 131072 KB Execution killed with signal 9
4 Correct 4022 ms 84036 KB Output is correct
5 Correct 4329 ms 72164 KB Output is correct
6 Correct 7588 ms 89444 KB Output is correct
7 Correct 5499 ms 59920 KB Output is correct
8 Execution timed out 8090 ms 115216 KB Time limit exceeded
9 Execution timed out 8089 ms 65204 KB Time limit exceeded
10 Execution timed out 8087 ms 102428 KB Time limit exceeded
11 Execution timed out 8016 ms 83160 KB Time limit exceeded
12 Runtime error 3631 ms 131072 KB Execution killed with signal 9
13 Runtime error 2739 ms 131072 KB Execution killed with signal 9
14 Runtime error 4259 ms 131072 KB Execution killed with signal 9
15 Runtime error 2642 ms 131072 KB Execution killed with signal 9
16 Runtime error 1199 ms 131072 KB Execution killed with signal 9
17 Runtime error 2910 ms 131072 KB Execution killed with signal 9