oj.uz

Submission #731623

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

vector<vector<int>> r, g;
vector<int> euler, in, out, fr, c;
vector<vector<pair<int, int>>> q;
int t;
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) {
    fr[c[euler[x]]]++;
}

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

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), q.resize(qq);
    map<pair<int, int>, int> ans;
    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++) 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 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 336 KB Output is correct
5 Correct 8 ms 464 KB Output is correct
6 Correct 45 ms 4204 KB Output is correct
7 Correct 61 ms 1864 KB Output is correct
8 Correct 86 ms 3016 KB Output is correct
9 Correct 262 ms 6600 KB Output is correct
10 Correct 711 ms 12276 KB Output is correct
11 Correct 637 ms 6252 KB Output is correct
12 Correct 1538 ms 14988 KB Output is correct
13 Correct 1183 ms 9440 KB Output is correct
14 Correct 907 ms 5368 KB Output is correct
15 Correct 1380 ms 9268 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3341 ms 11084 KB Output is correct
2 Correct 3571 ms 10784 KB Output is correct
3 Correct 4978 ms 16288 KB Output is correct
4 Runtime error 3570 ms 131072 KB Execution killed with signal 9
5 Runtime error 4400 ms 131072 KB Execution killed with signal 9
6 Runtime error 1633 ms 131072 KB Execution killed with signal 9
7 Runtime error 3275 ms 131072 KB Execution killed with signal 9
8 Runtime error 2788 ms 131072 KB Execution killed with signal 9
9 Runtime error 3038 ms 131072 KB Execution killed with signal 9
10 Runtime error 652 ms 131072 KB Execution killed with signal 9
11 Runtime error 960 ms 131072 KB Execution killed with signal 9
12 Runtime error 3183 ms 131072 KB Execution killed with signal 9
13 Runtime error 3076 ms 131072 KB Execution killed with signal 9
14 Runtime error 5710 ms 131072 KB Execution killed with signal 9
15 Runtime error 2958 ms 131072 KB Execution killed with signal 9
16 Runtime error 2586 ms 131072 KB Execution killed with signal 9
17 Runtime error 5430 ms 131072 KB Execution killed with signal 9