oj.uz

Submission #731678

# Submission time Handle Problem Language Result Execution time Memory
731678 2023-04-27T18:38:49 Z Desh03 Regions (IOI09_regions) C++17
30 / 100
 4253 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 (abs(i - j) <= 5000 && 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 4 ms 6864 KB Output is correct
2 Correct 4 ms 6864 KB Output is correct
3 Correct 8 ms 6864 KB Output is correct
4 Correct 7 ms 6992 KB Output is correct
5 Correct 10 ms 6992 KB Output is correct
6 Correct 20 ms 9148 KB Output is correct
7 Correct 32 ms 7740 KB Output is correct
8 Correct 50 ms 8428 KB Output is correct
9 Correct 78 ms 11524 KB Output is correct
10 Correct 133 ms 12808 KB Output is correct
11 Correct 180 ms 11192 KB Output is correct
12 Correct 324 ms 16356 KB Output is correct
13 Correct 166 ms 11304 KB Output is correct
14 Correct 225 ms 9956 KB Output is correct
15 Correct 354 ms 13224 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1537 ms 13032 KB Output is correct
2 Correct 863 ms 12048 KB Output is correct
3 Correct 1778 ms 16240 KB Output is correct
4 Runtime error 677 ms 131072 KB Execution killed with signal 9
5 Runtime error 832 ms 131072 KB Execution killed with signal 9
6 Runtime error 798 ms 131072 KB Execution killed with signal 9
7 Runtime error 828 ms 131072 KB Execution killed with signal 9
8 Runtime error 915 ms 131072 KB Execution killed with signal 9
9 Runtime error 1372 ms 131072 KB Execution killed with signal 9
10 Runtime error 916 ms 131072 KB Execution killed with signal 9
11 Runtime error 4253 ms 131072 KB Execution killed with signal 9
12 Runtime error 3478 ms 131072 KB Execution killed with signal 9
13 Runtime error 2180 ms 131072 KB Execution killed with signal 9
14 Runtime error 3000 ms 131072 KB Execution killed with signal 9
15 Runtime error 1010 ms 131072 KB Execution killed with signal 9
16 Runtime error 816 ms 131072 KB Execution killed with signal 9
17 Runtime error 1089 ms 131072 KB Execution killed with signal 9