Submission #805541

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
805541	2023-08-03T17:40:21 Z	Liudas	Regions (IOI09_regions)	C++17	Compilation error	0 ms	0 KB

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++;
}
struct node2{
    vector<short> arr;
    vector<int> child;
    int reg;
};
void dfs2(int head, vector<node2> &tree){
    for(int i : tree[head].child){
        dfs(i, tree);
        for(int j = 0; j < R; j ++){
            tree[head].arr[j] += tree[i].arr[j];
        }
    }
    tree[head].arr[tree[head].reg]++;
}
int main()
{
    int N, Q;
    cin >> N >> R >> Q;
    if(R< 500){
        vector<node2> tree(N);
        cin >> tree[0].reg;
        tree[0].reg--;
        tree[0].arr.assign(R, 0);
        for(int i = 1; i < N; i ++){
            tree[i].arr.assign(R, 0);
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            tree[a].child.push_back(i);
            tree[i].reg = b;
        }
        vector<vector<int>> table(R, vector<int> (R));
        dfs2(0, tree);
        for(auto j : tree){
            for(int i = 0; i < R; i ++){
                table[j.reg][i] += j.arr[i];
            }
        }
        while(Q--){
            int a, b;
            cin >> a >> b;
            a--;b--;
            cout << table[a][b] << endl;
        }
    }
    else{
        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

regions.cpp: In function 'void dfs2(int, std::vector<node2>&)':
regions.cpp:24:16: error: invalid initialization of reference of type 'std::vector<node>&' from expression of type 'std::vector<node2>'
   24 |         dfs(i, tree);
      |                ^~~~
regions.cpp:9:34: note: in passing argument 2 of 'void dfs(int, std::vector<node>&, int&)'
    9 | void dfs(int head, vector<node> &tree, int &c){
      |                    ~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'int main()':
regions.cpp:91:17: warning: unused variable 'last' [-Wunused-variable]
   91 |             int last = 0, lid = 0, cc = 0;
      |                 ^~~~
regions.cpp:91:27: warning: unused variable 'lid' [-Wunused-variable]
   91 |             int last = 0, lid = 0, cc = 0;
      |                           ^~~