oj.uz

Submission #731679

# Submission time Handle Problem Language Result Execution time Memory
731679 2023-04-27T18:39:33 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) <= 1000 && 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 6916 KB Output is correct
3 Correct 6 ms 6864 KB Output is correct
4 Correct 9 ms 6992 KB Output is correct
5 Correct 10 ms 6992 KB Output is correct
6 Correct 26 ms 9148 KB Output is correct
7 Correct 37 ms 7740 KB Output is correct
8 Correct 51 ms 8420 KB Output is correct
9 Correct 74 ms 11464 KB Output is correct
10 Correct 119 ms 12864 KB Output is correct
11 Correct 137 ms 11128 KB Output is correct
12 Correct 330 ms 16440 KB Output is correct
13 Correct 193 ms 11332 KB Output is correct
14 Correct 242 ms 9924 KB Output is correct
15 Correct 376 ms 13080 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1488 ms 12872 KB Output is correct
2 Correct 1177 ms 11984 KB Output is correct
3 Correct 1927 ms 16212 KB Output is correct
4 Incorrect 802 ms 63888 KB Output isn't correct
5 Incorrect 1381 ms 107436 KB Output isn't correct
6 Runtime error 1508 ms 131072 KB Execution killed with signal 9
7 Runtime error 1976 ms 131072 KB Execution killed with signal 9
8 Runtime error 1402 ms 131072 KB Execution killed with signal 9
9 Runtime error 3423 ms 131072 KB Execution killed with signal 9
10 Runtime error 1864 ms 131072 KB Execution killed with signal 9
11 Execution timed out 8016 ms 76172 KB Time limit exceeded
12 Execution timed out 8038 ms 98600 KB Time limit exceeded
13 Runtime error 5026 ms 131072 KB Execution killed with signal 9
14 Execution timed out 8032 ms 123316 KB Time limit exceeded
15 Runtime error 2286 ms 131072 KB Execution killed with signal 9
16 Runtime error 1589 ms 131072 KB Execution killed with signal 9
17 Runtime error 2219 ms 131072 KB Execution killed with signal 9