oj.uz

Submission #337342

# Submission time Handle Problem Language Result Execution time Memory
337342 2020-12-19T23:02:43 Z arbor Regions (IOI09_regions) C++17
100 / 100
 2929 ms 79332 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 2e5 + 5, MR = 2.5e4 + 5;
int N, R, Q, a[MN], sz[MN], tin[MN], tout[MN], tt;
int lb[MR], sub[MN], cnt1[450][MR], cnt2[MR][450];
vector<int> g[MN];
vector<pii> rg[MR];

void tour(int u) {
    tin[u] = ++tt;
    for (int v : g[u]) tour(v);
    tout[u] = tt;
    rg[a[u]].emplace_back(tin[u], tout[u]);
}

void go(int u, int r, int cnt) {
    cnt1[lb[r]][a[u]] += cnt;
    sub[u] = a[u] == r;
    for (int v : g[u]) {
        go(v, r, cnt + (a[v] == r));
        sub[u] += sub[v];
    }
    cnt2[a[u]][lb[r]] += sub[u];
}

int solve(int r1, int r2) {
    int p1 = 0, p2 = 0, ret = 0;
    stack<pii> st;
    while (p2 < rg[r2].size()) {
        if (p1 == rg[r1].size() || rg[r1][p1].first > rg[r2][p2].first) {
            while (!st.empty() && st.top().second < rg[r2][p2].first) st.pop();
            p2++;
            ret += st.size();
        } else if (rg[r1][p1].first < rg[r2][p2].first) {
            while (!st.empty() && st.top().second < rg[r1][p1].first) st.pop();
            st.push(rg[r1][p1]);
            p1++;
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> R >> Q >> a[1];
    int B = sqrt(N);
    for (int i = 2; i <= N; i++) {
        int p; cin >> p >> a[i];
        g[p].push_back(i);
        sz[a[i]]++;
    }
    tour(1);
    int id = 0;
    for (int i = 1; i <= R; i++) {
        if (sz[i] >= B) {
            lb[i] = ++id;
            go(1, i, a[1] == i);
        }
        sort(all(rg[i]));
    }
    for (int i = 0; i < Q; i++) {
        int r1, r2; cin >> r1 >> r2;
        if (sz[r1] >= B) cout << cnt1[lb[r1]][r2] << endl;
        else if (sz[r2] >= B) cout << cnt2[r1][lb[r2]] << endl;
        else cout << solve(r1, r2) << endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int solve(int, int)':
regions.cpp:32:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while (p2 < rg[r2].size()) {
      |            ~~~^~~~~~~~~~~~~~~
regions.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if (p1 == rg[r1].size() || rg[r1][p1].first > rg[r2][p2].first) {
      |             ~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5612 KB Output is correct
2 Correct 4 ms 5740 KB Output is correct
3 Correct 6 ms 5612 KB Output is correct
4 Correct 10 ms 5632 KB Output is correct
5 Correct 11 ms 5740 KB Output is correct
6 Correct 18 ms 5740 KB Output is correct
7 Correct 34 ms 5740 KB Output is correct
8 Correct 49 ms 5740 KB Output is correct
9 Correct 31 ms 5996 KB Output is correct
10 Correct 86 ms 6124 KB Output is correct
11 Correct 143 ms 6508 KB Output is correct
12 Correct 171 ms 7020 KB Output is correct
13 Correct 137 ms 6636 KB Output is correct
14 Correct 242 ms 7916 KB Output is correct
15 Correct 270 ms 12368 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1122 ms 11860 KB Output is correct
2 Correct 1223 ms 10104 KB Output is correct
3 Correct 2228 ms 14700 KB Output is correct
4 Correct 220 ms 7276 KB Output is correct
5 Correct 355 ms 8940 KB Output is correct
6 Correct 770 ms 23168 KB Output is correct
7 Correct 1024 ms 30060 KB Output is correct
8 Correct 1224 ms 39940 KB Output is correct
9 Correct 1772 ms 14940 KB Output is correct
10 Correct 2929 ms 78104 KB Output is correct
11 Correct 2722 ms 14532 KB Output is correct
12 Correct 1235 ms 45292 KB Output is correct
13 Correct 1811 ms 46044 KB Output is correct
14 Correct 2503 ms 53744 KB Output is correct
15 Correct 2570 ms 68324 KB Output is correct
16 Correct 2333 ms 79332 KB Output is correct
17 Correct 2457 ms 69752 KB Output is correct