oj.uz

Submission #805593

# Submission time Handle Problem Language Result Execution time Memory
805593 2023-08-03T18:18:52 Z Liudas Regions (IOI09_regions) C++17
100 / 100
 5851 ms 56360 KB 
#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>, int> ans;
        while(Q--){
            int a, b;
            cin >> a >> b;
            a--;b--;
            if(ans.find({a,b})!=ans.end()){
                cout<< ans[make_pair(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: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;
      |                           ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 7 ms 336 KB Output is correct
6 Correct 17 ms 976 KB Output is correct
7 Correct 23 ms 976 KB Output is correct
8 Correct 37 ms 1360 KB Output is correct
9 Correct 49 ms 4304 KB Output is correct
10 Correct 79 ms 10128 KB Output is correct
11 Correct 61 ms 10024 KB Output is correct
12 Correct 93 ms 20868 KB Output is correct
13 Correct 157 ms 18564 KB Output is correct
14 Correct 169 ms 15076 KB Output is correct
15 Correct 143 ms 25244 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 38008 KB Output is correct
2 Correct 711 ms 41584 KB Output is correct
3 Correct 1130 ms 56360 KB Output is correct
4 Correct 248 ms 4840 KB Output is correct
5 Correct 279 ms 7412 KB Output is correct
6 Correct 532 ms 7616 KB Output is correct
7 Correct 696 ms 8712 KB Output is correct
8 Correct 1118 ms 17724 KB Output is correct
9 Correct 1556 ms 24920 KB Output is correct
10 Correct 3461 ms 32560 KB Output is correct
11 Correct 3031 ms 30436 KB Output is correct
12 Correct 3163 ms 24632 KB Output is correct
13 Correct 3618 ms 26656 KB Output is correct
14 Correct 4402 ms 28336 KB Output is correct
15 Correct 5514 ms 35580 KB Output is correct
16 Correct 5851 ms 41636 KB Output is correct
17 Correct 4943 ms 39688 KB Output is correct