oj.uz

Submission #731669

# Submission time Handle Problem Language Result Execution time Memory
731669 2023-04-27T18:17:11 Z Desh03 Regions (IOI09_regions) C++17
35 / 100
 3837 ms 131072 KB 
#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(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);
    vector<unordered_map<short 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 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 2 ms 308 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 26 ms 2628 KB Output is correct
7 Correct 34 ms 1108 KB Output is correct
8 Correct 47 ms 1796 KB Output is correct
9 Correct 94 ms 4936 KB Output is correct
10 Correct 139 ms 6364 KB Output is correct
11 Correct 183 ms 4808 KB Output is correct
12 Correct 445 ms 10304 KB Output is correct
13 Correct 176 ms 5240 KB Output is correct
14 Correct 264 ms 4140 KB Output is correct
15 Correct 374 ms 7444 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1827 ms 8088 KB Output is correct
2 Correct 1505 ms 7336 KB Output is correct
3 Correct 2175 ms 11780 KB Output is correct
4 Correct 979 ms 129780 KB Output is correct
5 Runtime error 1076 ms 131072 KB Execution killed with signal 9
6 Runtime error 1016 ms 131072 KB Execution killed with signal 9
7 Runtime error 938 ms 131072 KB Execution killed with signal 9
8 Runtime error 1000 ms 131072 KB Execution killed with signal 9
9 Runtime error 1164 ms 131072 KB Execution killed with signal 9
10 Runtime error 647 ms 131072 KB Execution killed with signal 9
11 Runtime error 2906 ms 131072 KB Execution killed with signal 9
12 Runtime error 3837 ms 131072 KB Execution killed with signal 9
13 Runtime error 1496 ms 131072 KB Execution killed with signal 9
14 Runtime error 2439 ms 131072 KB Execution killed with signal 9
15 Runtime error 763 ms 131072 KB Execution killed with signal 9
16 Runtime error 610 ms 131072 KB Execution killed with signal 9
17 Runtime error 1308 ms 131072 KB Execution killed with signal 9