oj.uz

Submission #731680

# Submission time Handle Problem Language Result Execution time Memory
731680 2023-04-27T18:40:27 Z Desh03 Regions (IOI09_regions) C++17
30 / 100
 8000 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) <= 500 && 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 6 ms 6984 KB Output is correct
4 Correct 6 ms 7008 KB Output is correct
5 Correct 12 ms 6992 KB Output is correct
6 Correct 29 ms 9136 KB Output is correct
7 Correct 34 ms 7744 KB Output is correct
8 Correct 42 ms 8424 KB Output is correct
9 Correct 73 ms 11544 KB Output is correct
10 Correct 117 ms 12748 KB Output is correct
11 Correct 177 ms 11036 KB Output is correct
12 Correct 349 ms 16328 KB Output is correct
13 Correct 200 ms 11312 KB Output is correct
14 Correct 215 ms 9952 KB Output is correct
15 Correct 361 ms 13140 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1503 ms 12852 KB Output is correct
2 Correct 1532 ms 11996 KB Output is correct
3 Correct 2062 ms 16260 KB Output is correct
4 Incorrect 749 ms 38292 KB Output isn't correct
5 Incorrect 1093 ms 62924 KB Output isn't correct
6 Incorrect 1977 ms 78340 KB Output isn't correct
7 Incorrect 3828 ms 112036 KB Output isn't correct
8 Runtime error 2139 ms 131072 KB Execution killed with signal 9
9 Runtime error 6357 ms 131072 KB Execution killed with signal 9
10 Runtime error 3176 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8101 ms 46180 KB Time limit exceeded
12 Execution timed out 8087 ms 60856 KB Time limit exceeded
13 Execution timed out 8106 ms 113128 KB Time limit exceeded
14 Execution timed out 8083 ms 72960 KB Time limit exceeded
15 Runtime error 3605 ms 131072 KB Execution killed with signal 9
16 Runtime error 2323 ms 131072 KB Execution killed with signal 9
17 Runtime error 3545 ms 131072 KB Execution killed with signal 9