oj.uz

Submission #731662

# Submission time Handle Problem Language Result Execution time Memory
731662 2023-04-27T18:12:50 Z Desh03 Regions (IOI09_regions) C++17
35 / 100
 5626 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<unordered_map<int, int>> ans(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++)
                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 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 3 ms 336 KB Output is correct
5 Correct 9 ms 336 KB Output is correct
6 Correct 24 ms 2512 KB Output is correct
7 Correct 26 ms 1304 KB Output is correct
8 Correct 40 ms 1992 KB Output is correct
9 Correct 90 ms 5056 KB Output is correct
10 Correct 138 ms 6648 KB Output is correct
11 Correct 188 ms 5020 KB Output is correct
12 Correct 431 ms 10572 KB Output is correct
13 Correct 241 ms 5588 KB Output is correct
14 Correct 292 ms 4524 KB Output is correct
15 Correct 392 ms 8124 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1869 ms 10260 KB Output is correct
2 Correct 1530 ms 9728 KB Output is correct
3 Correct 2444 ms 15304 KB Output is correct
4 Correct 1607 ms 130304 KB Output is correct
5 Runtime error 1171 ms 131072 KB Execution killed with signal 9
6 Runtime error 1212 ms 131072 KB Execution killed with signal 9
7 Runtime error 1107 ms 131072 KB Execution killed with signal 9
8 Runtime error 1063 ms 131072 KB Execution killed with signal 9
9 Runtime error 1427 ms 131072 KB Execution killed with signal 9
10 Runtime error 737 ms 131072 KB Execution killed with signal 9
11 Runtime error 4244 ms 131072 KB Execution killed with signal 9
12 Runtime error 5626 ms 131072 KB Execution killed with signal 9
13 Runtime error 1844 ms 131072 KB Execution killed with signal 9
14 Runtime error 4732 ms 131072 KB Execution killed with signal 9
15 Runtime error 865 ms 131072 KB Execution killed with signal 9
16 Runtime error 684 ms 131072 KB Execution killed with signal 9
17 Runtime error 1361 ms 131072 KB Execution killed with signal 9