oj.uz

Submission #731535

# Submission time Handle Problem Language Result Execution time Memory
731535 2023-04-27T13:56:56 Z Desh03 Regions (IOI09_regions) C++17
40 / 100
 2033 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);
    vector<vector<int>> ans(rr, vector<int> (rr));
    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 3 ms 208 KB Output is correct
4 Correct 6 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 14 ms 700 KB Output is correct
7 Correct 33 ms 464 KB Output is correct
8 Correct 40 ms 720 KB Output is correct
9 Correct 62 ms 1360 KB Output is correct
10 Correct 132 ms 2004 KB Output is correct
11 Correct 171 ms 2048 KB Output is correct
12 Correct 310 ms 3268 KB Output is correct
13 Correct 209 ms 2712 KB Output is correct
14 Correct 233 ms 3144 KB Output is correct
15 Correct 277 ms 6060 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1670 ms 8900 KB Output is correct
2 Correct 1134 ms 8220 KB Output is correct
3 Correct 2033 ms 12488 KB Output is correct
4 Correct 915 ms 66268 KB Output is correct
5 Correct 1148 ms 103496 KB Output is correct
6 Runtime error 56 ms 131072 KB Execution killed with signal 9
7 Runtime error 60 ms 131072 KB Execution killed with signal 9
8 Runtime error 57 ms 131072 KB Execution killed with signal 9
9 Runtime error 52 ms 131072 KB Execution killed with signal 9
10 Runtime error 60 ms 131072 KB Execution killed with signal 9
11 Runtime error 58 ms 131072 KB Execution killed with signal 9
12 Runtime error 59 ms 131072 KB Execution killed with signal 9
13 Runtime error 58 ms 131072 KB Execution killed with signal 9
14 Runtime error 56 ms 131072 KB Execution killed with signal 9
15 Runtime error 57 ms 131072 KB Execution killed with signal 9
16 Runtime error 58 ms 131072 KB Execution killed with signal 9
17 Runtime error 55 ms 131072 KB Execution killed with signal 9