oj.uz

Submission #872150

# Submission time Handle Problem Language Result Execution time Memory
872150 2023-11-12T11:37:38 Z overwatch9 Regions (IOI09_regions) C++17
15 / 100
 8000 ms 77180 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 (){}
    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;
}
stree tree;
map <pair <int, int>, int> found;
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);
    tree = stree(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;
        if (found.find({r1, r2}) != found.end()) {
            cout << found[{r1, r2}] << endl;
            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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6804 KB Output is correct
4 Correct 3 ms 7136 KB Output is correct
5 Correct 7 ms 7384 KB Output is correct
6 Correct 17 ms 7992 KB Output is correct
7 Correct 32 ms 8508 KB Output is correct
8 Correct 60 ms 8948 KB Output is correct
9 Correct 129 ms 12060 KB Output is correct
10 Correct 442 ms 16672 KB Output is correct
11 Correct 622 ms 20816 KB Output is correct
12 Correct 1183 ms 25664 KB Output is correct
13 Correct 1510 ms 27276 KB Output is correct
14 Correct 1603 ms 32252 KB Output is correct
15 Correct 3000 ms 42096 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8041 ms 64156 KB Time limit exceeded
2 Execution timed out 8071 ms 67044 KB Time limit exceeded
3 Execution timed out 8080 ms 77180 KB Time limit exceeded
4 Execution timed out 8071 ms 34464 KB Time limit exceeded
5 Execution timed out 8061 ms 40884 KB Time limit exceeded
6 Execution timed out 8029 ms 37800 KB Time limit exceeded
7 Execution timed out 8069 ms 38828 KB Time limit exceeded
8 Execution timed out 8025 ms 53540 KB Time limit exceeded
9 Execution timed out 8053 ms 64196 KB Time limit exceeded
10 Execution timed out 8090 ms 72200 KB Time limit exceeded
11 Runtime error 65 ms 26456 KB Execution killed with signal 11
12 Execution timed out 8064 ms 72928 KB Time limit exceeded
13 Execution timed out 8016 ms 72936 KB Time limit exceeded
14 Runtime error 71 ms 29400 KB Execution killed with signal 11
15 Runtime error 66 ms 35592 KB Execution killed with signal 11
16 Runtime error 76 ms 42232 KB Execution killed with signal 11
17 Runtime error 68 ms 40908 KB Execution killed with signal 11