oj.uz

Submission #731675

# Submission time Handle Problem Language Result Execution time Memory
731675 2023-04-27T18:31:55 Z Desh03 Regions (IOI09_regions) C++17
30 / 100
 1863 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

unordered_map<short int, int> ans[25000];
vector<int> r[25000], g[200000], euler;
int in[200000], out[200000], fr[25000];
short int c[200000];
int t;
const short int block = 447;

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

void add(int x) {
    fr[euler[x]]++;
}

void remove(int x) {
    fr[euler[x]]--;
}

int main() {
    int n, rr, qq;
    cin >> n >> rr >> qq;
    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;
        });
    }
    for (int i = 0; i < rr; i++) {
        int lb, rb;
        if (r[i].size()) lb = in[r[i][0]] + 1, rb = lb - 1;
        for (int u : r[i]) {
            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--);
            for (int j = 0; j < rr; j++)
                if (fr[j]) ans[i][j] += fr[j];
        }
        if (r[i].size()) for (int j = 0; j < rr; j++) fr[j] = 0;
    }
    while (qq--) {
        int a, b;
        cin >> a >> b;
        cout << ans[--a][--b] << endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6864 KB Output is correct
2 Correct 4 ms 6864 KB Output is correct
3 Correct 6 ms 6864 KB Output is correct
4 Correct 6 ms 7012 KB Output is correct
5 Correct 11 ms 6992 KB Output is correct
6 Correct 17 ms 9160 KB Output is correct
7 Correct 19 ms 7748 KB Output is correct
8 Correct 36 ms 8540 KB Output is correct
9 Correct 73 ms 11464 KB Output is correct
10 Correct 124 ms 12744 KB Output is correct
11 Correct 161 ms 11080 KB Output is correct
12 Correct 314 ms 16444 KB Output is correct
13 Correct 153 ms 11300 KB Output is correct
14 Correct 218 ms 10024 KB Output is correct
15 Correct 246 ms 13128 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1316 ms 13016 KB Output is correct
2 Correct 1119 ms 12064 KB Output is correct
3 Correct 1863 ms 16316 KB Output is correct
4 Runtime error 631 ms 131072 KB Execution killed with signal 9
5 Runtime error 800 ms 131072 KB Execution killed with signal 9
6 Runtime error 673 ms 131072 KB Execution killed with signal 9
7 Runtime error 634 ms 131072 KB Execution killed with signal 9
8 Runtime error 799 ms 131072 KB Execution killed with signal 9
9 Runtime error 810 ms 131072 KB Execution killed with signal 9
10 Runtime error 532 ms 131072 KB Execution killed with signal 9
11 Runtime error 1640 ms 131072 KB Execution killed with signal 9
12 Runtime error 1804 ms 131072 KB Execution killed with signal 9
13 Runtime error 1012 ms 131072 KB Execution killed with signal 9
14 Runtime error 1628 ms 131072 KB Execution killed with signal 9
15 Runtime error 600 ms 131072 KB Execution killed with signal 9
16 Runtime error 499 ms 131072 KB Execution killed with signal 9
17 Runtime error 989 ms 131072 KB Execution killed with signal 9