oj.uz

Submission #805511

# Submission time Handle Problem Language Result Execution time Memory
805511 2023-08-03T17:18:42 Z Liudas Regions (IOI09_regions) C++17
0 / 100
 8000 ms 38004 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<set<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].insert(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());
    }
    while(Q--){
        int a, b;
        cin >> a >> b;
        a--;b--;
        int last = 0, lid = 0, cc = 0;
        for(auto [l, r] : ranges[a]){
            last = max(l, last);
            for(; last <= r; last ++){
                if(regions[b].find(last) != regions[b].end()){
                    cc ++;
                }
            }
        }
        cout << cc << endl;
    }
    return 0;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:48:23: warning: unused variable 'lid' [-Wunused-variable]
   48 |         int last = 0, lid = 0, cc = 0;
      |                       ^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 288 KB Output isn't correct
2 Incorrect 1 ms 208 KB Output isn't correct
3 Incorrect 2 ms 208 KB Output isn't correct
4 Incorrect 3 ms 208 KB Output isn't correct
5 Incorrect 8 ms 336 KB Output isn't correct
6 Incorrect 15 ms 460 KB Output isn't correct
7 Incorrect 35 ms 464 KB Output isn't correct
8 Incorrect 46 ms 596 KB Output isn't correct
9 Incorrect 132 ms 1232 KB Output isn't correct
10 Incorrect 162 ms 1616 KB Output isn't correct
11 Incorrect 775 ms 2384 KB Output isn't correct
12 Incorrect 1391 ms 3308 KB Output isn't correct
13 Incorrect 366 ms 3304 KB Output isn't correct
14 Incorrect 2171 ms 4304 KB Output isn't correct
15 Incorrect 5288 ms 7624 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8082 ms 11012 KB Time limit exceeded
2 Execution timed out 8100 ms 10268 KB Time limit exceeded
3 Execution timed out 8010 ms 14032 KB Time limit exceeded
4 Incorrect 2110 ms 4660 KB Output isn't correct
5 Incorrect 5374 ms 6892 KB Output isn't correct
6 Execution timed out 8093 ms 7824 KB Time limit exceeded
7 Execution timed out 8074 ms 10524 KB Time limit exceeded
8 Execution timed out 8071 ms 17848 KB Time limit exceeded
9 Execution timed out 8023 ms 22756 KB Time limit exceeded
10 Execution timed out 8029 ms 29560 KB Time limit exceeded
11 Execution timed out 8074 ms 27016 KB Time limit exceeded
12 Execution timed out 8068 ms 27328 KB Time limit exceeded
13 Execution timed out 8016 ms 27592 KB Time limit exceeded
14 Execution timed out 8055 ms 28328 KB Time limit exceeded
15 Execution timed out 8064 ms 32616 KB Time limit exceeded
16 Execution timed out 8086 ms 38004 KB Time limit exceeded
17 Execution timed out 8070 ms 36872 KB Time limit exceeded