Submission #805523

#	Time	Username	Problem	Language	Result	Execution time	Memory
805523		Liudas	Regions (IOI09_regions)	C++17	65 / 100	8047 ms	29432 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){
        //cout << i.l << " " << i.r << " " << i.num << endl;
        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]){
            for(int lid = 0; lid < regions[b].size(); lid++){
                if(regions[b][lid] <= r && regions[b][lid] >= l){
                    cc ++;
                }
                if(regions[b][lid] > r){break;}
            }
        }
        cout << cc << endl;
    }
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:51:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for(int lid = 0; lid < regions[b].size(); lid++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:49:13: warning: unused variable 'last' [-Wunused-variable]
   49 |         int last = 0, lid = 0, cc = 0;
      |             ^~~~
regions.cpp:49:23: warning: unused variable 'lid' [-Wunused-variable]
   49 |         int last = 0, lid = 0, cc = 0;
      |                       ^~~

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