Submission #805592

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
805592	2023-08-03T18:18:06 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){
        dfs2(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());
        }
        map<pair<int, int>> ans;
        while(Q--){
            int a, b;
            cin >> a >> b;
            a--;b--;
            if(ans.find({a,b})!=ans.end()){
                cout<< ans[{a,b}] << endl;
                continue;
            }
            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();
            }
            ans[{a, b}] = cc;
            cout << cc << endl;
        }
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:87:26: error: wrong number of template arguments (1, should be at least 2)
   87 |         map<pair<int, int>> ans;
      |                          ^~
In file included from /usr/include/c++/10/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from regions.cpp:1:
/usr/include/c++/10/bits/stl_map.h:100:11: note: provided for 'template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map'
  100 |     class map
      |           ^~~
regions.cpp:92:20: error: request for member 'find' in 'ans', which is of non-class type 'int'
   92 |             if(ans.find({a,b})!=ans.end()){
      |                    ^~~~
regions.cpp:92:37: error: request for member 'end' in 'ans', which is of non-class type 'int'
   92 |             if(ans.find({a,b})!=ans.end()){
      |                                     ^~~
regions.cpp:93:27: error: invalid types 'int[<brace-enclosed initializer list>]' for array subscript
   93 |                 cout<< ans[{a,b}] << endl;
      |                           ^
regions.cpp:101:16: error: invalid types 'int[<brace-enclosed initializer list>]' for array subscript
  101 |             ans[{a, b}] = cc;
      |                ^
regions.cpp:96:17: warning: unused variable 'last' [-Wunused-variable]
   96 |             int last = 0, lid = 0, cc = 0;
      |                 ^~~~
regions.cpp:96:27: warning: unused variable 'lid' [-Wunused-variable]
   96 |             int last = 0, lid = 0, cc = 0;
      |                           ^~~