oj.uz

Submission #872143

# Submission time Handle Problem Language Result Execution time Memory
872143 2023-11-12T11:32:40 Z overwatch9 Regions (IOI09_regions) C++17
1 / 100
 8000 ms 76260 KB 
#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
using namespace std;
struct stree {
    #define lc v*2
    #define rc v*2+1
    vector <unordered_map <int, int>> tree;
    stree (int s) {
        tree.resize(s * 4);
    }
    void pushup(int v) {
        if (tree[rc].size() < tree[lc].size()) {
            tree[v] = tree[lc];
            for (auto i : tree[rc])
                tree[v][i.first] += i.second;
        } else {
            tree[v] = tree[rc];
            for (auto i : tree[lc])
                tree[v][i.first] += i.second;
        }
    }
    void update(int v, int tl, int tr, int p, int val) {
        if (tl > p || tr < p)
            return;
        if (tl == tr) {
            tree[v][val]++;
            return;
        }
        int tm = (tl + tr) / 2;
        update(lc, tl, tm, p, val);
        update(rc, tm+1, tr, p, val);
        pushup(v);
    }
    int query(int v, int tl, int tr, int l, int r, int val) {
        if (tl > r || tr < l)
            return 0;
        if (tl >= l && tr <= r) {
            if (tree[v].find(val) != tree[v].end())
                return tree[v][val];
            return 0;
        }
        int tm = (tl + tr) / 2;
        int a = query(lc, tl, tm, l, r, val);
        int b = query(rc, tm+1, tr, l, r, val);
        return a + b;
    }
};
const int maxn = 2e5;
int visit[maxn], finish[maxn], region[maxn];
vector <int> adj[maxn];
int t = 0;
void dfs(int s, int p) {
    visit[s] = t++;
    for (auto i : adj[s])
        dfs(i, s);
    finish[s] = t;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, r, q;
    cin >> n >> r >> q;
    vector <vector <int>> cities(r+1);
    cin >> region[1];
    cities[region[1]].push_back(1);
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        adj[x].push_back(i);
        cin >> region[i];
        cities[region[i]].push_back(i);
    }
    dfs(1, 1);
    stree tree(t+1);
    for (int i = 1; i <= n; i++)
        tree.update(1, 0, t, visit[i], region[i]);
    map <pair <int, int>, int> found;
    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;
        if (found.find({r1, r2}) != found.end()) {
            cout << found[{r1, r2}] << '\n';
            continue;
        }
        int ans = 0;
        for (auto i : cities[r1]) {
            ans += tree.query(1, 0, t, visit[i], finish[i]-1, r2);
        }
        found[{r1, r2}] = ans;
        cout << ans << endl;
    }
}

Subtask #1
1.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Execution timed out 1 ms 6744 KB Time limit exceeded (wall clock)
3 Execution timed out 2 ms 6800 KB Time limit exceeded (wall clock)
4 Execution timed out 2 ms 6744 KB Time limit exceeded (wall clock)
5 Execution timed out 3 ms 7128 KB Time limit exceeded (wall clock)
6 Execution timed out 7 ms 7448 KB Time limit exceeded (wall clock)
7 Execution timed out 20 ms 8352 KB Time limit exceeded (wall clock)
8 Execution timed out 23 ms 8616 KB Time limit exceeded (wall clock)
9 Execution timed out 77 ms 11524 KB Time limit exceeded (wall clock)
10 Execution timed out 337 ms 15408 KB Time limit exceeded (wall clock)
11 Execution timed out 415 ms 18940 KB Time limit exceeded (wall clock)
12 Execution timed out 801 ms 23904 KB Time limit exceeded (wall clock)
13 Execution timed out 1119 ms 26992 KB Time limit exceeded (wall clock)
14 Execution timed out 759 ms 30996 KB Time limit exceeded (wall clock)
15 Execution timed out 828 ms 40784 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1784 ms 62060 KB Time limit exceeded (wall clock)
2 Execution timed out 2060 ms 64712 KB Time limit exceeded (wall clock)
3 Execution timed out 2551 ms 76260 KB Time limit exceeded (wall clock)
4 Execution timed out 8026 ms 34884 KB Time limit exceeded
5 Execution timed out 7792 ms 42024 KB Time limit exceeded (wall clock)
6 Execution timed out 8100 ms 38484 KB Time limit exceeded
7 Execution timed out 8023 ms 39192 KB Time limit exceeded
8 Execution timed out 8019 ms 53832 KB Time limit exceeded
9 Execution timed out 8087 ms 64516 KB Time limit exceeded
10 Execution timed out 8026 ms 72652 KB Time limit exceeded
11 Runtime error 53 ms 26572 KB Execution killed with signal 11
12 Execution timed out 8055 ms 73608 KB Time limit exceeded
13 Execution timed out 8058 ms 73524 KB Time limit exceeded
14 Runtime error 71 ms 29276 KB Execution killed with signal 11
15 Runtime error 68 ms 35600 KB Execution killed with signal 11
16 Runtime error 70 ms 42152 KB Execution killed with signal 11
17 Runtime error 69 ms 40464 KB Execution killed with signal 11