oj.uz

Submission #914022

# Submission time Handle Problem Language Result Execution time Memory
914022 2024-01-20T19:24:12 Z asdasdqwer Regions (IOI09_regions) C++14
100 / 100
 2958 ms 113680 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 500 KB Output is correct
6 Correct 9 ms 1168 KB Output is correct
7 Correct 15 ms 848 KB Output is correct
8 Correct 17 ms 1160 KB Output is correct
9 Correct 26 ms 2076 KB Output is correct
10 Correct 52 ms 2792 KB Output is correct
11 Correct 75 ms 2616 KB Output is correct
12 Correct 86 ms 3804 KB Output is correct
13 Correct 104 ms 4204 KB Output is correct
14 Correct 152 ms 4448 KB Output is correct
15 Correct 199 ms 7856 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 19736 KB Output is correct
2 Correct 732 ms 16788 KB Output is correct
3 Correct 1362 ms 22772 KB Output is correct
4 Correct 159 ms 5260 KB Output is correct
5 Correct 254 ms 8140 KB Output is correct
6 Correct 510 ms 33112 KB Output is correct
7 Correct 560 ms 18320 KB Output is correct
8 Correct 1032 ms 99340 KB Output is correct
9 Correct 1746 ms 24584 KB Output is correct
10 Correct 2958 ms 113680 KB Output is correct
11 Correct 2856 ms 29500 KB Output is correct
12 Correct 1029 ms 25664 KB Output is correct
13 Correct 1333 ms 28780 KB Output is correct
14 Correct 1766 ms 61468 KB Output is correct
15 Correct 2505 ms 40868 KB Output is correct
16 Correct 2352 ms 52976 KB Output is correct
17 Correct 2599 ms 81812 KB Output is correct