oj.uz

Submission #241847

# Submission time Handle Problem Language Result Execution time Memory
241847 2020-06-25T23:23:56 Z thecodingwizard Regions (IOI09_regions) C++11
65 / 100
 8000 ms 62104 KB 
#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, 
             rb_tree_tag, tree_order_statistics_node_update>; 

int n, r, q; 
int R[200000];
vector<int> adj[200000];
vector<int> A[200001];
int start[200000], End[200000];
Tree<int> regions[200001];

int ctr = 0;
void dfs(int u) {
    start[u] = ctr;
    for (int v : adj[u]) {
        dfs(v);
    }
    End[u] = ctr++;
    regions[R[u]].insert(End[u]);
}

int main() {
    cin >> n >> r >> q;

    for (int i = 0; i < n; i++) {
        if (i == 0) {
            cin >> R[i];
        } else {
            int p;
            cin >> p >> R[i];
            adj[p-1].push_back(i);
        }
        A[R[i]].push_back(i);
    }

    dfs(0);

    map<pair<int, int>, long long> cache;
    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;
        if (cache.count(make_pair(a, b))) {
            cout << cache[make_pair(a, b)] << endl;
            continue;
        }
        bool swapped = false;
        if (A[a].size() > A[b].size()) {
            //swap(a, b);
            //swapped = true;
        }
        long long ans = 0;
        for (int n : A[a]) {
            int x = start[n], y = End[n];
            ans += regions[b].order_of_key(y) - regions[b].order_of_key(x);
        }
        cout << ans << endl;
        if (swapped) swap(a, b);
        cache[make_pair(a, b)] = ans;
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25344 KB Output is correct
2 Correct 25 ms 25472 KB Output is correct
3 Correct 27 ms 25472 KB Output is correct
4 Correct 30 ms 25472 KB Output is correct
5 Correct 31 ms 25508 KB Output is correct
6 Correct 45 ms 25600 KB Output is correct
7 Correct 67 ms 25720 KB Output is correct
8 Correct 64 ms 25800 KB Output is correct
9 Correct 96 ms 26432 KB Output is correct
10 Correct 154 ms 26744 KB Output is correct
11 Correct 190 ms 27408 KB Output is correct
12 Correct 213 ms 28280 KB Output is correct
13 Correct 257 ms 28204 KB Output is correct
14 Correct 406 ms 29176 KB Output is correct
15 Correct 359 ms 32120 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2101 ms 35208 KB Output is correct
2 Correct 2566 ms 34180 KB Output is correct
3 Correct 3482 ms 39672 KB Output is correct
4 Correct 359 ms 29772 KB Output is correct
5 Correct 603 ms 32328 KB Output is correct
6 Correct 794 ms 32376 KB Output is correct
7 Correct 1050 ms 33172 KB Output is correct
8 Correct 2025 ms 42548 KB Output is correct
9 Correct 4226 ms 48968 KB Output is correct
10 Correct 7790 ms 56520 KB Output is correct
11 Execution timed out 8077 ms 54036 KB Time limit exceeded
12 Execution timed out 8038 ms 48664 KB Time limit exceeded
13 Execution timed out 8045 ms 49544 KB Time limit exceeded
14 Execution timed out 8028 ms 49156 KB Time limit exceeded
15 Execution timed out 8028 ms 54368 KB Time limit exceeded
16 Execution timed out 8051 ms 62104 KB Time limit exceeded
17 Execution timed out 8057 ms 61068 KB Time limit exceeded