oj.uz

Submission #722840

# Submission time Handle Problem Language Result Execution time Memory
722840 2023-04-13T01:56:57 Z horiseun Regions (IOI09_regions) C++11
45 / 100
 4182 ms 49816 KB 
#include <iostream>
#include <vector>
#include <map>
#include <tuple>
#include <algorithm>
using namespace std;

const int SQRT = 500;

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]]) - lower_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 7 ms 5584 KB Output is correct
5 Correct 9 ms 5584 KB Output is correct
6 Correct 19 ms 5584 KB Output is correct
7 Correct 23 ms 5584 KB Output is correct
8 Correct 33 ms 5712 KB Output is correct
9 Correct 47 ms 6096 KB Output is correct
10 Correct 83 ms 6096 KB Output is correct
11 Correct 121 ms 6480 KB Output is correct
12 Correct 147 ms 6944 KB Output is correct
13 Correct 187 ms 6864 KB Output is correct
14 Correct 236 ms 7200 KB Output is correct
15 Correct 266 ms 9676 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1795 ms 10632 KB Output isn't correct
2 Incorrect 1999 ms 10368 KB Output isn't correct
3 Incorrect 2953 ms 12352 KB Output isn't correct
4 Correct 281 ms 7376 KB Output is correct
5 Correct 323 ms 8856 KB Output is correct
6 Incorrect 1125 ms 16176 KB Output isn't correct
7 Correct 1444 ms 9868 KB Output is correct
8 Incorrect 1140 ms 16516 KB Output isn't correct
9 Correct 1934 ms 15040 KB Output is correct
10 Correct 4182 ms 19132 KB Output is correct
11 Correct 3504 ms 17084 KB Output is correct
12 Incorrect 1461 ms 18296 KB Output isn't correct
13 Incorrect 2076 ms 19128 KB Output isn't correct
14 Incorrect 2741 ms 41164 KB Output isn't correct
15 Incorrect 3133 ms 23732 KB Output isn't correct
16 Incorrect 2589 ms 29244 KB Output isn't correct
17 Incorrect 3538 ms 49816 KB Output isn't correct