Submission #914022

#	Time	Username	Problem	Language	Result	Execution time	Memory
914022		asdasdqwer	Regions (IOI09_regions)	C++14	100 / 100	2958 ms	113680 KiB

regions

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,r,q;cin>>n>>r>>q;
    vector<vector<int>> regions(r);
    int f;cin>>f;f--;regions[f].push_back(0);
    vector<vector<int>> child(n);
    for (int i=1;i<n;i++) {
        int p;cin>>p;p--;
        child[p].push_back(i);
        int rr;cin>>rr;rr--;
        regions[rr].push_back(i);
    }

    vector<bool> gg(r, false);

    for (int i=0;i<r;i++) {
        if (regions[i].size() >= 447) {
            gg[i] = true;
        }
    }

    vector<int> ord, sz(n, 1);
    function<void(int)> dfs=[&](int node) {
        ord.push_back(node);
        for (int x:child[node]) {
            dfs(x);
            sz[node]+=sz[x];
        }
    };

    dfs(0);

    function<void(int,vector<int>&)> dpdown=[&](int node, vector<int> &dp) {
        for (int x:child[node]) {
            dpdown(x, dp);
        }

        for (int x:child[node]) {
            dp[node] += dp[x];
        }
    };

    function<void(int,vector<int>&)> dpup=[&](int node, vector<int> &dp) {
        for (int x:child[node]) {
            dp[x] += dp[node];
            dpup(x, dp);
        }
    };

    vector<int> idx(n, -1);
    for (int i=0;i<n;i++) {
        idx[ord[i]]=i;
    }

    vector<vector<int>> ups(r), downs(r);
    for (int i=0;i<r;i++) {
        if (!gg[i])continue;
        vector<int> ones(n,0);
        for (int x:regions[i]) {
            ones[x]=1;
        }

        dpup(0, ones);
        ups[i] = ones;
    }

    vector<vector<int>> srtidx(r);
    for (int i=0;i<r;i++) {
        if (gg[i])continue;
        for (int x:regions[i]) {
            srtidx[i].push_back(idx[x]);
        }
        sort(srtidx[i].begin(), srtidx[i].end());
    }

    for (int i=0;i<r;i++) {
        if (!gg[i])continue;
        vector<int> ones(n,0);
        for (int x:regions[i]) {
            ones[x]=1;
        }

        dpdown(0, ones);
        downs[i] = ones;
    }

    map<array<int,2>,int> sol;
    while (q--) {
        int r1, r2;cin>>r1>>r2;
        r1--;r2--;

        if (sol.find({r1, r2}) == sol.end()) {
            int res=0;
            if (gg[r1] && gg[r2]) {
                for (int x:regions[r1]) {
                    res += downs[r2][x];
                }
            }

            else if (gg[r1] && !gg[r2]) {
                for (int x:regions[r2]) {
                    res += ups[r1][x];
                }
            }

            else if (!gg[r1] && gg[r2]) {
                for (int x:regions[r1]) {
                    res += downs[r2][x];
                }

            }

            else {
                for (int x:regions[r1]) {
                    int start = idx[x];
                    int end = start + sz[x];

                    auto it1 = upper_bound(srtidx[r2].begin(), srtidx[r2].end(), start);
                    if (it1 == srtidx[r2].end() || *it1 >= end) {
                        continue;
                    }

                    auto it2 = prev(lower_bound(srtidx[r2].begin(), srtidx[r2].end(), end));
                    res += distance(it1, it2) + 1;
                }
            }

            sol[{r1, r2}] = res;
        }

        cout<<sol[{r1, r2}]<<"\n";
        cout.flush();
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85