oj.uz

Submission #928544

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

const int MaxN = 1e5 + 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[u]][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 2 ms 8280 KB Output is correct
2 Correct 2 ms 8280 KB Output is correct
3 Correct 2 ms 8280 KB Output is correct
4 Correct 3 ms 8280 KB Output is correct
5 Correct 5 ms 8280 KB Output is correct
6 Correct 9 ms 8280 KB Output is correct
7 Correct 13 ms 8244 KB Output is correct
8 Correct 15 ms 8280 KB Output is correct
9 Correct 25 ms 8796 KB Output is correct
10 Correct 45 ms 8792 KB Output is correct
11 Correct 75 ms 9068 KB Output is correct
12 Correct 77 ms 9304 KB Output is correct
13 Correct 132 ms 9100 KB Output is correct
14 Correct 213 ms 9664 KB Output is correct
15 Correct 198 ms 12088 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1387 ms 12492 KB Output isn't correct
2 Incorrect 1550 ms 11300 KB Output isn't correct
3 Incorrect 2218 ms 14176 KB Output isn't correct
4 Correct 183 ms 9956 KB Output is correct
5 Correct 210 ms 11248 KB Output is correct
6 Correct 1097 ms 10524 KB Output is correct
7 Correct 1200 ms 11360 KB Output is correct
8 Correct 929 ms 16192 KB Output is correct
9 Runtime error 32 ms 20096 KB Execution killed with signal 6
10 Runtime error 32 ms 24872 KB Execution killed with signal 11
11 Runtime error 30 ms 18184 KB Execution killed with signal 11
12 Runtime error 32 ms 20404 KB Execution killed with signal 6
13 Runtime error 31 ms 19916 KB Execution killed with signal 6
14 Runtime error 30 ms 19716 KB Execution killed with signal 6
15 Runtime error 29 ms 21028 KB Execution killed with signal 6
16 Runtime error 33 ms 25060 KB Execution killed with signal 11
17 Runtime error 32 ms 24812 KB Execution killed with signal 11