oj.uz

Submission #242137

# Submission time Handle Problem Language Result Execution time Memory
242137 2020-06-27T01:26:37 Z thecodingwizard Regions (IOI09_regions) C++11
3 / 100
 7095 ms 75960 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 start2[200000], End2[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) {
    start2[u] = ctr++;
    regions2Ct[R[u]]++;
    regions2[R[u]].push_back({start2[u], regions2Ct[R[u]]});
    for (int v : adj[u]) {
        dfs2(v);
    }
    regions2Ct[R[u]]--;
    End2[u] = ctr;
    regions2[R[u]].push_back({End2[u], 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(start2[n], -1));
                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
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 30080 KB Output isn't correct
2 Incorrect 27 ms 30080 KB Output isn't correct
3 Incorrect 28 ms 30072 KB Output isn't correct
4 Incorrect 31 ms 30080 KB Output isn't correct
5 Incorrect 34 ms 30208 KB Output isn't correct
6 Correct 44 ms 30336 KB Output is correct
7 Incorrect 47 ms 30428 KB Output isn't correct
8 Incorrect 61 ms 30584 KB Output isn't correct
9 Correct 83 ms 31352 KB Output is correct
10 Incorrect 94 ms 31868 KB Output isn't correct
11 Incorrect 221 ms 32504 KB Output isn't correct
12 Incorrect 212 ms 33656 KB Output isn't correct
13 Incorrect 259 ms 33632 KB Output isn't correct
14 Incorrect 469 ms 34680 KB Output isn't correct
15 Correct 483 ms 38264 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1645 ms 41504 KB Output isn't correct
2 Incorrect 1891 ms 41064 KB Output isn't correct
3 Incorrect 3224 ms 46876 KB Output isn't correct
4 Incorrect 377 ms 35448 KB Output isn't correct
5 Incorrect 618 ms 38176 KB Output isn't correct
6 Incorrect 761 ms 38732 KB Output isn't correct
7 Incorrect 1083 ms 40376 KB Output isn't correct
8 Incorrect 1534 ms 50040 KB Output isn't correct
9 Incorrect 3662 ms 58864 KB Output isn't correct
10 Incorrect 6319 ms 66156 KB Output isn't correct
11 Incorrect 7095 ms 65664 KB Output isn't correct
12 Incorrect 2717 ms 59124 KB Output isn't correct
13 Incorrect 3428 ms 61312 KB Output isn't correct
14 Incorrect 4228 ms 63340 KB Output isn't correct
15 Incorrect 5478 ms 70356 KB Output isn't correct
16 Incorrect 5781 ms 75960 KB Output isn't correct
17 Incorrect 5610 ms 74608 KB Output isn't correct