oj.uz

Submission #722835

# Submission time Handle Problem Language Result Execution time Memory
722835 2023-04-13T01:46:49 Z horiseun Regions (IOI09_regions) C++11
35 / 100
 4789 ms 99736 KB 
#include <iostream>
#include <vector>
#include <map>
#include <tuple>
#include <algorithm>
using namespace std;

const int SQRT = 450;

int n, r, q, region[200005], in[200005], out[200005], idx;
vector<int> adj[200005], blocks[25005], dfsorder, pref;
map<pair<int, int>, int> ans;

void dfs(int curr, int par) {
    in[curr] = ++idx;
    blocks[region[curr]].push_back(idx);
    dfsorder.push_back(curr);
    for (int i : adj[curr]) {
        if (i == par) continue;
        dfs(i, curr);
    }
    out[curr] = idx;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> r >> q >> region[1];
    for (int i = 2, x; i <= n; i++) {
        cin >> x >> region[i];
        adj[x].push_back(i);
        adj[i].push_back(x);
    }

    idx = -1;
    dfs(1, -1);
    for (int i = 1; i <= r; i++) {
        if (blocks[i].size() >= SQRT) {
            pref.resize(idx + 5, 0);
            for (int j : blocks[i]) {
                pref[j]++;
                pref[out[dfsorder[j]] + 1]--;
            }
            for (int j = 1; j <= idx; j++) {
                pref[j] += pref[j - 1];
                ans[{i, region[dfsorder[j]]}] += pref[j];
            }
        }
    }

    for (int i = 0, r1, r2, ret; i < q; i++) {
        cin >> r1 >> r2;
        if (blocks[r1].size() >= SQRT) {
            cout << ans[{r1, r2}] << "\n" << flush;
        } else {
            ret = 0;
            for (int j : blocks[r1]) {
                ret += upper_bound(blocks[r2].begin(), blocks[r2].end(), out[dfsorder[j]]) - upper_bound(blocks[r2].begin(), blocks[r2].end(), j); 
            }
            cout << ret << "\n" << flush;
        }
    }

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5584 KB Output is correct
2 Correct 3 ms 5584 KB Output is correct
3 Correct 6 ms 5584 KB Output is correct
4 Correct 8 ms 5584 KB Output is correct
5 Correct 11 ms 5584 KB Output is correct
6 Correct 24 ms 5584 KB Output is correct
7 Correct 34 ms 5712 KB Output is correct
8 Correct 41 ms 5712 KB Output is correct
9 Correct 46 ms 6096 KB Output is correct
10 Correct 81 ms 6096 KB Output is correct
11 Correct 127 ms 6472 KB Output is correct
12 Correct 146 ms 6880 KB Output is correct
13 Correct 186 ms 6900 KB Output is correct
14 Correct 257 ms 7248 KB Output is correct
15 Correct 274 ms 9596 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1859 ms 10768 KB Output isn't correct
2 Incorrect 1676 ms 10432 KB Output isn't correct
3 Incorrect 2514 ms 12404 KB Output isn't correct
4 Correct 270 ms 7376 KB Output is correct
5 Correct 356 ms 8912 KB Output is correct
6 Incorrect 894 ms 32096 KB Output isn't correct
7 Incorrect 1622 ms 18744 KB Output isn't correct
8 Incorrect 2294 ms 77484 KB Output isn't correct
9 Correct 2145 ms 15092 KB Output is correct
10 Incorrect 4789 ms 99736 KB Output isn't correct
11 Correct 3018 ms 17004 KB Output is correct
12 Incorrect 1213 ms 18364 KB Output isn't correct
13 Incorrect 1931 ms 19176 KB Output isn't correct
14 Incorrect 2552 ms 41052 KB Output isn't correct
15 Incorrect 3137 ms 23824 KB Output isn't correct
16 Incorrect 3147 ms 29244 KB Output isn't correct
17 Incorrect 3637 ms 49848 KB Output isn't correct