oj.uz

Submission #805542

# Submission time Handle Problem Language Result Execution time Memory
805542 2023-08-03T17:40:56 Z Liudas Regions (IOI09_regions) C++17
100 / 100
 7759 ms 56436 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());
        }
        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 '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;
      |                           ^~~

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 2 ms 208 KB Output is correct
4 Correct 5 ms 208 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 17 ms 976 KB Output is correct
7 Correct 27 ms 976 KB Output is correct
8 Correct 32 ms 1360 KB Output is correct
9 Correct 37 ms 4304 KB Output is correct
10 Correct 82 ms 10124 KB Output is correct
11 Correct 102 ms 10064 KB Output is correct
12 Correct 108 ms 20948 KB Output is correct
13 Correct 154 ms 18640 KB Output is correct
14 Correct 148 ms 15224 KB Output is correct
15 Correct 200 ms 25192 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 38016 KB Output is correct
2 Correct 794 ms 41516 KB Output is correct
3 Correct 1077 ms 56436 KB Output is correct
4 Correct 261 ms 3280 KB Output is correct
5 Correct 361 ms 5200 KB Output is correct
6 Correct 1123 ms 5636 KB Output is correct
7 Correct 1236 ms 7612 KB Output is correct
8 Correct 1026 ms 13652 KB Output is correct
9 Correct 1826 ms 16696 KB Output is correct
10 Correct 3474 ms 22548 KB Output is correct
11 Correct 3028 ms 18768 KB Output is correct
12 Correct 3286 ms 19224 KB Output is correct
13 Correct 3890 ms 19432 KB Output is correct
14 Correct 5048 ms 19992 KB Output is correct
15 Correct 5168 ms 24408 KB Output is correct
16 Correct 5369 ms 29532 KB Output is correct
17 Correct 7759 ms 28360 KB Output is correct