제출 #928545

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
928545		HuyAT	Regions (IOI09_regions)	C++14	100 / 100	3352 ms	34772 KiB

regions

#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 / 15
• Subtask 2: 85 / 85