oj.uz

Submission #872137

# Submission time Handle Problem Language Result Execution time Memory
872137 2023-11-12T11:19:59 Z overwatch9 Regions (IOI09_regions) C++17
15 / 100
 8000 ms 75976 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) {
        tree[v] = tree[lc];
        for (auto i : tree[rc])
            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() {
    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 6744 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 3 ms 6744 KB Output is correct
4 Correct 4 ms 6744 KB Output is correct
5 Correct 8 ms 7000 KB Output is correct
6 Correct 17 ms 7256 KB Output is correct
7 Correct 38 ms 7768 KB Output is correct
8 Correct 58 ms 8328 KB Output is correct
9 Correct 133 ms 10832 KB Output is correct
10 Correct 584 ms 15036 KB Output is correct
11 Correct 812 ms 18716 KB Output is correct
12 Correct 1577 ms 23840 KB Output is correct
13 Correct 1909 ms 26384 KB Output is correct
14 Correct 1894 ms 30540 KB Output is correct
15 Correct 3221 ms 40024 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8084 ms 62204 KB Time limit exceeded
2 Execution timed out 8074 ms 64696 KB Time limit exceeded
3 Execution timed out 8102 ms 75976 KB Time limit exceeded
4 Execution timed out 8026 ms 28700 KB Time limit exceeded
5 Execution timed out 8029 ms 37912 KB Time limit exceeded
6 Execution timed out 8063 ms 36112 KB Time limit exceeded
7 Execution timed out 8042 ms 35792 KB Time limit exceeded
8 Execution timed out 8023 ms 53228 KB Time limit exceeded
9 Execution timed out 8039 ms 63300 KB Time limit exceeded
10 Execution timed out 8069 ms 70984 KB Time limit exceeded
11 Runtime error 113 ms 26560 KB Execution killed with signal 11
12 Execution timed out 8092 ms 71064 KB Time limit exceeded
13 Execution timed out 8099 ms 69564 KB Time limit exceeded
14 Runtime error 114 ms 29280 KB Execution killed with signal 11
15 Runtime error 128 ms 35840 KB Execution killed with signal 11
16 Runtime error 115 ms 42288 KB Execution killed with signal 11
17 Runtime error 113 ms 40596 KB Execution killed with signal 11