oj.uz

Submission #928545

# Submission time Handle Problem Language Result Execution time Memory
928545 2024-02-16T15:52:40 Z HuyAT Regions (IOI09_regions) C++14
100 / 100
 3352 ms 34772 KB 
#include<bits/stdc++.h>

const int MaxN = 2e5 + 10;
const int blockSize = 500;
const int MaxR = 25000;

std::vector<int> adj[MaxN + 1],v[MaxN + 1],typeEle[MaxR + 1],spe;
int n,r,q,cnt[MaxR + 1],type[MaxN + 1],timeIn[MaxN + 1],timeOut[MaxN + 1],idx[MaxN + 1];
int ans[MaxN / blockSize + 1][MaxR + 1];

void readData(){
    std::cin >> n >> r >> q;
    for(int i = 1;i <= n;++i){
        if(i > 1){
            int h;
            std::cin >> h;
            adj[h].emplace_back(i);
        }
        std::cin >> type[i];
        typeEle[type[i]].emplace_back(i);
    }
}
void precompute(){
    int t = 0;
    for(int i = 1;i <= r;++i){
        if((int)typeEle[i].size() > blockSize){
            idx[i] = ++t;
            spe.emplace_back(i);
        }
    }
}
void dfs(int u = 1){
    static int timer = 0;
    for(int val : spe){
        ans[idx[val]][type[u]] += cnt[val];
    }
    timeIn[u] = ++timer;
    v[type[u]].emplace_back(timeIn[u]);
    ++cnt[type[u]];
    for(int v : adj[u]){
        dfs(v);
    }
    timeOut[u] = ++timer;
    --cnt[type[u]];
}
void solve(){
    for(int i = 1;i <= q;++i){
        int r,r1;
        std::cin >> r >> r1;
        long long curAns = 0;
        if(idx[r] == 0){
            for(int val : typeEle[r]){
                int it = std::lower_bound(v[r1].begin(),v[r1].end(),timeIn[val]) - v[r1].begin();
                int it1 = std::upper_bound(v[r1].begin(),v[r1].end(),timeOut[val]) - v[r1].begin();
                curAns += it1 - it;
            }
        }else{
            curAns = ans[idx[r]][r1];
        }
        std::cout << curAns << std::endl;
    }
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    precompute();
    dfs();
    solve();
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13912 KB Output is correct
2 Correct 3 ms 13656 KB Output is correct
3 Correct 3 ms 13656 KB Output is correct
4 Correct 4 ms 13656 KB Output is correct
5 Correct 6 ms 13656 KB Output is correct
6 Correct 13 ms 13656 KB Output is correct
7 Correct 14 ms 13656 KB Output is correct
8 Correct 22 ms 13908 KB Output is correct
9 Correct 27 ms 14204 KB Output is correct
10 Correct 43 ms 14168 KB Output is correct
11 Correct 78 ms 14420 KB Output is correct
12 Correct 80 ms 14680 KB Output is correct
13 Correct 133 ms 14424 KB Output is correct
14 Correct 205 ms 14988 KB Output is correct
15 Correct 185 ms 17404 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1401 ms 19540 KB Output is correct
2 Correct 1555 ms 18364 KB Output is correct
3 Correct 2100 ms 21168 KB Output is correct
4 Correct 159 ms 15032 KB Output is correct
5 Correct 242 ms 16472 KB Output is correct
6 Correct 1058 ms 15960 KB Output is correct
7 Correct 1266 ms 16828 KB Output is correct
8 Correct 1002 ms 21508 KB Output is correct
9 Correct 1651 ms 21424 KB Output is correct
10 Correct 3297 ms 26088 KB Output is correct
11 Correct 3352 ms 20688 KB Output is correct
12 Correct 908 ms 24288 KB Output is correct
13 Correct 1309 ms 24476 KB Output is correct
14 Correct 1388 ms 26296 KB Output is correct
15 Correct 2247 ms 28624 KB Output is correct
16 Correct 1951 ms 33748 KB Output is correct
17 Correct 2000 ms 34772 KB Output is correct