oj.uz

Submission #872138

# Submission time Handle Problem Language Result Execution time Memory
872138 2023-11-12T11:22:40 Z overwatch9 Regions (IOI09_regions) C++17
15 / 100
 8000 ms 76036 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() {
    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 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 4 ms 6744 KB Output is correct
5 Correct 6 ms 7000 KB Output is correct
6 Correct 18 ms 7256 KB Output is correct
7 Correct 34 ms 7820 KB Output is correct
8 Correct 54 ms 8280 KB Output is correct
9 Correct 124 ms 10936 KB Output is correct
10 Correct 580 ms 15148 KB Output is correct
11 Correct 766 ms 18764 KB Output is correct
12 Correct 1347 ms 23996 KB Output is correct
13 Correct 1789 ms 26100 KB Output is correct
14 Correct 1637 ms 30384 KB Output is correct
15 Correct 2748 ms 40120 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8063 ms 62348 KB Time limit exceeded
2 Execution timed out 8007 ms 64724 KB Time limit exceeded
3 Execution timed out 8087 ms 76036 KB Time limit exceeded
4 Execution timed out 8045 ms 29296 KB Time limit exceeded
5 Execution timed out 8029 ms 38408 KB Time limit exceeded
6 Execution timed out 8055 ms 36544 KB Time limit exceeded
7 Execution timed out 8023 ms 35840 KB Time limit exceeded
8 Execution timed out 8077 ms 53884 KB Time limit exceeded
9 Execution timed out 8092 ms 63972 KB Time limit exceeded
10 Execution timed out 8041 ms 71588 KB Time limit exceeded
11 Runtime error 51 ms 26520 KB Execution killed with signal 11
12 Execution timed out 8029 ms 70876 KB Time limit exceeded
13 Execution timed out 8016 ms 69740 KB Time limit exceeded
14 Runtime error 69 ms 29300 KB Execution killed with signal 11
15 Runtime error 64 ms 35780 KB Execution killed with signal 11
16 Runtime error 62 ms 42304 KB Execution killed with signal 11
17 Runtime error 68 ms 40488 KB Execution killed with signal 11