oj.uz

Submission #805528

# Submission time Handle Problem Language Result Execution time Memory
805528 2023-08-03T17:33:35 Z Liudas Regions (IOI09_regions) C++17
80 / 100
 8000 ms 29536 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++;
}
int main()
{
    int N, Q;
    cin >> N >> R >> Q;
    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:48:13: warning: unused variable 'last' [-Wunused-variable]
   48 |         int last = 0, lid = 0, cc = 0;
      |             ^~~~
regions.cpp:48:23: warning: unused variable 'lid' [-Wunused-variable]
   48 |         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 208 KB Output is correct
3 Correct 2 ms 208 KB Output is correct
4 Correct 2 ms 208 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 14 ms 336 KB Output is correct
7 Correct 23 ms 336 KB Output is correct
8 Correct 29 ms 464 KB Output is correct
9 Correct 35 ms 976 KB Output is correct
10 Correct 68 ms 1232 KB Output is correct
11 Correct 94 ms 1744 KB Output is correct
12 Correct 121 ms 2384 KB Output is correct
13 Correct 142 ms 2256 KB Output is correct
14 Correct 233 ms 3152 KB Output is correct
15 Correct 236 ms 6108 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8032 ms 7988 KB Time limit exceeded
2 Execution timed out 8064 ms 7108 KB Time limit exceeded
3 Execution timed out 8071 ms 10412 KB Time limit exceeded
4 Correct 280 ms 3280 KB Output is correct
5 Correct 274 ms 5200 KB Output is correct
6 Correct 1170 ms 5632 KB Output is correct
7 Correct 1320 ms 7616 KB Output is correct
8 Correct 882 ms 13652 KB Output is correct
9 Correct 1938 ms 16696 KB Output is correct
10 Correct 3294 ms 22544 KB Output is correct
11 Correct 2818 ms 18756 KB Output is correct
12 Correct 3441 ms 19228 KB Output is correct
13 Correct 3831 ms 19436 KB Output is correct
14 Correct 5369 ms 19988 KB Output is correct
15 Correct 5704 ms 24356 KB Output is correct
16 Correct 6358 ms 29536 KB Output is correct
17 Execution timed out 8053 ms 28288 KB Time limit exceeded