Submission #722840

#	Time	Username	Problem	Language	Result	Execution time	Memory
722840		horiseun	Regions (IOI09_regions)	C++11	45 / 100	4182 ms	49816 KiB

regions

#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 / 15
• Subtask 2: 30 / 85