oj.uz

Submission #731673

# Submission time Handle Problem Language Result Execution time Memory
731673 2023-04-27T18:25:23 Z Desh03 Regions (IOI09_regions) C++17
0 / 100
 181 ms 50728 KB 
#pragma pack(1)
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> r, g;
vector<int> euler, in, out, fr;
vector<short int> c;
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;
    g.resize(n), r.resize(rr), in.resize(n), out.resize(n), fr.resize(rr), c.resize(n);
    vector<unordered_map<short 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++)
                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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 336 KB Execution killed with signal 11
2 Runtime error 1 ms 336 KB Execution killed with signal 11
3 Runtime error 1 ms 336 KB Execution killed with signal 11
4 Runtime error 1 ms 336 KB Execution killed with signal 11
5 Runtime error 1 ms 464 KB Execution killed with signal 11
6 Runtime error 1 ms 592 KB Execution killed with signal 11
7 Runtime error 1 ms 592 KB Execution killed with signal 11
8 Runtime error 2 ms 720 KB Execution killed with signal 11
9 Runtime error 4 ms 1744 KB Execution killed with signal 11
10 Runtime error 7 ms 2000 KB Execution killed with signal 11
11 Runtime error 12 ms 2832 KB Execution killed with signal 11
12 Runtime error 13 ms 4176 KB Execution killed with signal 11
13 Runtime error 20 ms 3628 KB Execution killed with signal 11
14 Runtime error 21 ms 4992 KB Execution killed with signal 11
15 Runtime error 36 ms 10568 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 13096 KB Execution killed with signal 11
2 Runtime error 60 ms 10872 KB Execution killed with signal 11
3 Runtime error 75 ms 17352 KB Execution killed with signal 11
4 Runtime error 25 ms 5312 KB Execution killed with signal 11
5 Runtime error 28 ms 8900 KB Execution killed with signal 11
6 Runtime error 41 ms 8772 KB Execution killed with signal 11
7 Runtime error 57 ms 11604 KB Execution killed with signal 11
8 Runtime error 76 ms 23016 KB Execution killed with signal 11
9 Runtime error 127 ms 25884 KB Execution killed with signal 11
10 Runtime error 150 ms 37096 KB Execution killed with signal 11
11 Runtime error 157 ms 27844 KB Execution killed with signal 11
12 Runtime error 174 ms 30552 KB Execution killed with signal 11
13 Runtime error 160 ms 30804 KB Execution killed with signal 11
14 Runtime error 177 ms 30856 KB Execution killed with signal 11
15 Runtime error 181 ms 39632 KB Execution killed with signal 11
16 Runtime error 180 ms 50728 KB Execution killed with signal 11
17 Runtime error 181 ms 48088 KB Execution killed with signal 11