oj.uz

Submission #805523

# Submission time Handle Problem Language Result Execution time Memory
805523 2023-08-03T17:30:15 Z Liudas Regions (IOI09_regions) C++17
65 / 100
 8000 ms 29432 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){
        //cout << i.l << " " << i.r << " " << i.num << endl;
        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]){
            for(int lid = 0; lid < regions[b].size(); lid++){
                if(regions[b][lid] <= r && regions[b][lid] >= l){
                    cc ++;
                }
                if(regions[b][lid] > r){break;}
            }
        }
        cout << cc << endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:51:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             for(int lid = 0; lid < regions[b].size(); lid++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~
regions.cpp:49:13: warning: unused variable 'last' [-Wunused-variable]
   49 |         int last = 0, lid = 0, cc = 0;
      |             ^~~~
regions.cpp:49:23: warning: unused variable 'lid' [-Wunused-variable]
   49 |         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 1 ms 208 KB Output is correct
4 Correct 4 ms 208 KB Output is correct
5 Correct 6 ms 336 KB Output is correct
6 Correct 16 ms 336 KB Output is correct
7 Correct 33 ms 336 KB Output is correct
8 Correct 30 ms 464 KB Output is correct
9 Correct 43 ms 976 KB Output is correct
10 Correct 67 ms 1232 KB Output is correct
11 Correct 94 ms 1744 KB Output is correct
12 Correct 119 ms 2384 KB Output is correct
13 Correct 170 ms 2328 KB Output is correct
14 Correct 267 ms 3096 KB Output is correct
15 Correct 345 ms 6096 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8004 ms 8000 KB Time limit exceeded
2 Execution timed out 8047 ms 7036 KB Time limit exceeded
3 Execution timed out 8044 ms 10388 KB Time limit exceeded
4 Correct 244 ms 3296 KB Output is correct
5 Correct 238 ms 5184 KB Output is correct
6 Correct 2412 ms 5632 KB Output is correct
7 Correct 1553 ms 7620 KB Output is correct
8 Correct 1374 ms 13644 KB Output is correct
9 Correct 2062 ms 16692 KB Output is correct
10 Correct 5712 ms 22548 KB Output is correct
11 Correct 5062 ms 18764 KB Output is correct
12 Correct 6048 ms 19224 KB Output is correct
13 Correct 6488 ms 19428 KB Output is correct
14 Execution timed out 8016 ms 19940 KB Time limit exceeded
15 Execution timed out 8006 ms 24440 KB Time limit exceeded
16 Execution timed out 8023 ms 29432 KB Time limit exceeded
17 Execution timed out 8047 ms 28352 KB Time limit exceeded