oj.uz

Submission #731708

# Submission time Handle Problem Language Result Execution time Memory
731708 2023-04-27T20:29:57 Z Desh03 Regions (IOI09_regions) C++17
35 / 100
 8000 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> r, g;
vector<int> euler, in, out, fr, c;
int t, cnt, b;
const 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) {
    cnt += c[euler[x]] == b;
}

void remove(int x) {
    cnt -= c[euler[x]] == b;
}

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);
    int x, h;
    cin >> h;
    h--;
    r[h].push_back(0);
    c[0] = h;
    vector<unordered_map<int, int>> mp(n);
    vector<unordered_map<short int, int>> mp2(rr);
    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;
        });
    }
    while (qq--) {
        int a, ans = 0;
        cin >> a >> b;
        a--, b--, cnt = 0;
        if (mp2[a].find(b) != mp2[a].end()) {
            cout << mp2[a][b] << '\n';
            continue;
        }
        int lb, rb;
        if (r[a].size()) lb = in[r[a][0]] + 1, rb = lb - 1;
        for (int u : r[a]) {
            if (mp[u].find(b) != mp[u].end()) cnt += mp[u][b];
            else {
                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--);
                mp[u][b] = cnt;
                ans += cnt;
            }
        }
        cout << ans << endl;
        mp2[a][b] = ans;
    }
}

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 208 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 11 ms 720 KB Output is correct
6 Correct 19 ms 764 KB Output is correct
7 Correct 40 ms 1760 KB Output is correct
8 Correct 48 ms 2160 KB Output is correct
9 Correct 117 ms 4984 KB Output is correct
10 Correct 307 ms 10080 KB Output is correct
11 Correct 808 ms 25768 KB Output is correct
12 Correct 1422 ms 26056 KB Output is correct
13 Correct 1286 ms 44652 KB Output is correct
14 Correct 2246 ms 89280 KB Output is correct
15 Correct 2507 ms 125264 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 2531 ms 131072 KB Execution killed with signal 9
2 Runtime error 1799 ms 131072 KB Execution killed with signal 9
3 Runtime error 2131 ms 131072 KB Execution killed with signal 9
4 Correct 3578 ms 74572 KB Output is correct
5 Correct 3910 ms 67600 KB Output is correct
6 Correct 7223 ms 80156 KB Output is correct
7 Correct 5487 ms 58904 KB Output is correct
8 Execution timed out 8021 ms 118588 KB Time limit exceeded
9 Execution timed out 8039 ms 69636 KB Time limit exceeded
10 Execution timed out 8096 ms 108768 KB Time limit exceeded
11 Execution timed out 8098 ms 93228 KB Time limit exceeded
12 Runtime error 2909 ms 131072 KB Execution killed with signal 9
13 Runtime error 2223 ms 131072 KB Execution killed with signal 9
14 Runtime error 3723 ms 131072 KB Execution killed with signal 9
15 Runtime error 2064 ms 131072 KB Execution killed with signal 9
16 Runtime error 928 ms 131072 KB Execution killed with signal 9
17 Runtime error 2562 ms 131072 KB Execution killed with signal 9