oj.uz

Submission #805579

# Submission time Handle Problem Language Result Execution time Memory
805579 2023-08-03T18:01:38 Z Liudas Regions (IOI09_regions) C++17
95 / 100
 8000 ms 56908 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")
#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:93:17: warning: unused variable 'last' [-Wunused-variable]
   93 |             int last = 0, lid = 0, cc = 0;
      |                 ^~~~
regions.cpp:93:27: warning: unused variable 'lid' [-Wunused-variable]
   93 |             int last = 0, lid = 0, cc = 0;
      |                           ^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 3 ms 208 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 13 ms 976 KB Output is correct
7 Correct 30 ms 976 KB Output is correct
8 Correct 21 ms 1360 KB Output is correct
9 Correct 21 ms 4304 KB Output is correct
10 Correct 82 ms 10132 KB Output is correct
11 Correct 107 ms 10152 KB Output is correct
12 Correct 144 ms 20864 KB Output is correct
13 Correct 146 ms 18616 KB Output is correct
14 Correct 135 ms 15144 KB Output is correct
15 Correct 169 ms 25864 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 38164 KB Output is correct
2 Correct 757 ms 41532 KB Output is correct
3 Correct 1055 ms 56908 KB Output is correct
4 Correct 261 ms 3300 KB Output is correct
5 Correct 369 ms 4792 KB Output is correct
6 Correct 1273 ms 5528 KB Output is correct
7 Correct 1704 ms 7488 KB Output is correct
8 Correct 1257 ms 12348 KB Output is correct
9 Correct 1943 ms 16336 KB Output is correct
10 Correct 3919 ms 20852 KB Output is correct
11 Correct 3848 ms 18712 KB Output is correct
12 Correct 4146 ms 19164 KB Output is correct
13 Correct 5024 ms 19068 KB Output is correct
14 Correct 6046 ms 19868 KB Output is correct
15 Correct 7291 ms 23068 KB Output is correct
16 Correct 7774 ms 25912 KB Output is correct
17 Execution timed out 8031 ms 25132 KB Time limit exceeded