Submission #805528

#	Time	Username	Problem	Language	Result	Execution time	Memory
805528		Liudas	Regions (IOI09_regions)	C++17	80 / 100	8071 ms	29536 KiB

regions

#include <bits/stdc++.h>
using namespace std;
struct node{
    int l, r, num;
    vector<int> child;
    int reg;
};
int R;
void dfs(int head, vector<node> &tree, int &c){
    tree[head].l = c;
    for(int i : tree[head].child){
        dfs(i, tree, c);
    }
    tree[head].r = c;
    tree[head].num = c++;
}
int main()
{
    int N, Q;
    cin >> N >> R >> Q;
    vector<node> tree(N);
    cin >> tree[0].reg;
    tree[0].reg--;
    for(int i = 1; i < N; i ++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        tree[a].child.push_back(i);
        tree[i].reg = b;
    }
    int c = 0;
    dfs(0, tree, c);
    vector<vector<int>> regions(R);
    vector<vector<pair<int, int>>> ranges(R);
    for(node i : tree){
        regions[i.reg].push_back(i.num);
        ranges[i.reg].push_back({i.l,i.r});
    }
    for(int i = 0; i < R; i ++){
        sort(ranges[i].begin(), ranges[i].end());
        sort(regions[i].begin(), regions[i].end());
    }
    while(Q--){
        int a, b;
        cin >> a >> b;
        a--;b--;
        int last = 0, lid = 0, cc = 0;
        for(auto [l, r] : ranges[a]){
            cc += upper_bound(regions[b].begin(), regions[b].end(), r)-regions[b].begin();
            cc -= lower_bound(regions[b].begin(), regions[b].end(), l)-regions[b].begin();
        }
        cout << cc << endl;
    }
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:48:13: warning: unused variable 'last' [-Wunused-variable]
   48 |         int last = 0, lid = 0, cc = 0;
      |             ^~~~
regions.cpp:48:23: warning: unused variable 'lid' [-Wunused-variable]
   48 |         int last = 0, lid = 0, cc = 0;
      |                       ^~~

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