Submission #805511

#	Time	Username	Problem	Language	Result	Execution time	Memory
805511		Liudas	Regions (IOI09_regions)	C++17	0 / 100	8100 ms	38004 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<set<int>> regions(R);
    vector<vector<pair<int, int>>> ranges(R);
    for(node i : tree){
        //cout << i.l << " " << i.r << " " << i.num << endl;
        regions[i.reg].insert(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());
    }
    while(Q--){
        int a, b;
        cin >> a >> b;
        a--;b--;
        int last = 0, lid = 0, cc = 0;
        for(auto [l, r] : ranges[a]){
            last = max(l, last);
            for(; last <= r; last ++){
                if(regions[b].find(last) != regions[b].end()){
                    cc ++;
                }
            }
        }
        cout << cc << endl;
    }
    return 0;
}

Compilation message (stderr)

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

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