oj.uz

Submission #872142

# Submission time Handle Problem Language Result Execution time Memory
872142 2023-11-12T11:26:49 Z overwatch9 Regions (IOI09_regions) C++17
15 / 100
 8000 ms 76044 KB 
#include <iostream>
#include <vector>
#include <unordered_map>
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]);
    while (q--) {
        int r1, r2;
        cin >> r1 >> r2;
        int ans = 0;
        for (auto i : cities[r1]) {
            ans += tree.query(1, 0, t, visit[i], finish[i]-1, r2);
        }
        cout << ans << endl;
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6740 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 3 ms 6744 KB Output is correct
5 Correct 8 ms 7252 KB Output is correct
6 Correct 15 ms 7256 KB Output is correct
7 Correct 31 ms 7868 KB Output is correct
8 Correct 44 ms 8364 KB Output is correct
9 Correct 124 ms 10832 KB Output is correct
10 Correct 427 ms 15144 KB Output is correct
11 Correct 596 ms 18876 KB Output is correct
12 Correct 1099 ms 23968 KB Output is correct
13 Correct 1416 ms 26264 KB Output is correct
14 Correct 1463 ms 30276 KB Output is correct
15 Correct 2592 ms 40052 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8071 ms 62072 KB Time limit exceeded
2 Execution timed out 8093 ms 64716 KB Time limit exceeded
3 Execution timed out 8012 ms 76044 KB Time limit exceeded
4 Execution timed out 8044 ms 33552 KB Time limit exceeded
5 Execution timed out 8020 ms 41052 KB Time limit exceeded
6 Execution timed out 8013 ms 38208 KB Time limit exceeded
7 Execution timed out 8095 ms 39132 KB Time limit exceeded
8 Execution timed out 8055 ms 53824 KB Time limit exceeded
9 Execution timed out 8096 ms 65116 KB Time limit exceeded
10 Execution timed out 8061 ms 72424 KB Time limit exceeded
11 Runtime error 65 ms 26556 KB Execution killed with signal 11
12 Execution timed out 8045 ms 73536 KB Time limit exceeded
13 Execution timed out 8053 ms 73604 KB Time limit exceeded
14 Runtime error 67 ms 29372 KB Execution killed with signal 11
15 Runtime error 60 ms 35808 KB Execution killed with signal 11
16 Runtime error 59 ms 42204 KB Execution killed with signal 11
17 Runtime error 63 ms 40528 KB Execution killed with signal 11