oj.uz

Submission #242139

# Submission time Handle Problem Language Result Execution time Memory
242139 2020-06-27T01:30:37 Z thecodingwizard Regions (IOI09_regions) C++11
100 / 100
 6979 ms 75072 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 id[200000];
vector<pair<int, int>> regions2[200001];
int regions2Ct[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 ctr2 = 0;
void dfs2(int u) {
    id[u] = ctr++;
    regions2Ct[R[u]]++;
    regions2[R[u]].push_back({id[u], regions2Ct[R[u]]});
    for (int v : adj[u]) {
        dfs2(v);
    }
    regions2Ct[R[u]]--;
    regions2[R[u]].push_back({ctr, regions2Ct[R[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);
        regions2Ct[R[i]] = 0;
    }

    dfs(0);
    dfs2(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]) {
            if (!swapped) {
                int x = start[n], y = End[n];
                ans += regions[b].order_of_key(y) - regions[b].order_of_key(x);
            } else {
                auto it = lower_bound(regions2[b].begin(), regions2[b].end(), make_pair(id[n], 1000000));
                if (it == regions2[b].begin()) continue;
                ans += (--it)->second;
            }
        }
        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 28 ms 30208 KB Output is correct
2 Correct 28 ms 30080 KB Output is correct
3 Correct 28 ms 30072 KB Output is correct
4 Correct 32 ms 30080 KB Output is correct
5 Correct 36 ms 30184 KB Output is correct
6 Correct 44 ms 30352 KB Output is correct
7 Correct 67 ms 30456 KB Output is correct
8 Correct 69 ms 30584 KB Output is correct
9 Correct 106 ms 31388 KB Output is correct
10 Correct 117 ms 31712 KB Output is correct
11 Correct 181 ms 32524 KB Output is correct
12 Correct 230 ms 33544 KB Output is correct
13 Correct 310 ms 33624 KB Output is correct
14 Correct 401 ms 34608 KB Output is correct
15 Correct 380 ms 37940 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1870 ms 41280 KB Output is correct
2 Correct 1775 ms 40668 KB Output is correct
3 Correct 3429 ms 46512 KB Output is correct
4 Correct 330 ms 35448 KB Output is correct
5 Correct 645 ms 38008 KB Output is correct
6 Correct 680 ms 38396 KB Output is correct
7 Correct 1065 ms 40248 KB Output is correct
8 Correct 2053 ms 49500 KB Output is correct
9 Correct 3385 ms 58292 KB Output is correct
10 Correct 6072 ms 65580 KB Output is correct
11 Correct 6979 ms 64580 KB Output is correct
12 Correct 2641 ms 58380 KB Output is correct
13 Correct 3336 ms 60608 KB Output is correct
14 Correct 4082 ms 62476 KB Output is correct
15 Correct 5115 ms 69536 KB Output is correct
16 Correct 6703 ms 75072 KB Output is correct
17 Correct 5680 ms 73832 KB Output is correct