oj.uz

Submission #967867

# Submission time Handle Problem Language Result Execution time Memory
967867 2024-04-23T03:19:55 Z ttamx Regions (IOI09_regions) C++17
100 / 100
 3681 ms 109324 KB 
#include<bits/stdc++.h>
#define all(x) begin(x),end(x)

using namespace std;

const int N=2e5+5;
const int K=320;
const int M=650;

int n,r,q,cnt;
int a[N],id[N];
long long dp[M][N];
vector<int> adj[N],comp[N],comp2[N];
int tin[N],tout[N];
int timer;

void tour(int u){
    tin[u]=++timer;
    comp2[a[u]].emplace_back(timer);
    for(auto v:adj[u])tour(v);
    tout[u]=timer;
}

void dfs(int u,int i,int c=0){
    if(a[u]==i)c++;
    else dp[id[i]][a[u]]+=c;
    for(auto v:adj[u])dfs(v,i,c);
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> r >> q;
    for(int i=1;i<=n;i++){
        if(i>1){
            int p;
            cin >> p;
            adj[p].emplace_back(i);
        }
        cin >> a[i];
        comp[a[i]].emplace_back(i);
    }
    tour(1);
    for(int i=1;i<=r;i++)if(comp[i].size()>K){
        id[i]=++cnt;
        dfs(1,i);
    }
    while(q--){
        int r1,r2;
        cin >> r1 >> r2;
        if(id[r1])cout << dp[id[r1]][r2] << endl;
        else{
            long long ans=0;
            for(auto u:comp[r1])ans+=upper_bound(all(comp2[r2]),tout[u])-lower_bound(all(comp2[r2]),tin[u]);
            cout << ans << endl;
        }
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 5 ms 18776 KB Output is correct
3 Correct 6 ms 18776 KB Output is correct
4 Correct 5 ms 18776 KB Output is correct
5 Correct 9 ms 18776 KB Output is correct
6 Correct 13 ms 18776 KB Output is correct
7 Correct 20 ms 18776 KB Output is correct
8 Correct 20 ms 19032 KB Output is correct
9 Correct 40 ms 19288 KB Output is correct
10 Correct 62 ms 19288 KB Output is correct
11 Correct 91 ms 19612 KB Output is correct
12 Correct 96 ms 19916 KB Output is correct
13 Correct 126 ms 19728 KB Output is correct
14 Correct 216 ms 20236 KB Output is correct
15 Correct 200 ms 22260 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1490 ms 57736 KB Output is correct
2 Correct 1699 ms 42152 KB Output is correct
3 Correct 2318 ms 40924 KB Output is correct
4 Correct 200 ms 20492 KB Output is correct
5 Correct 234 ms 21448 KB Output is correct
6 Correct 421 ms 90040 KB Output is correct
7 Correct 950 ms 84220 KB Output is correct
8 Correct 754 ms 91584 KB Output is correct
9 Correct 1914 ms 26852 KB Output is correct
10 Correct 2575 ms 109324 KB Output is correct
11 Correct 3681 ms 26468 KB Output is correct
12 Correct 998 ms 32248 KB Output is correct
13 Correct 1579 ms 32268 KB Output is correct
14 Correct 1947 ms 62824 KB Output is correct
15 Correct 2779 ms 36464 KB Output is correct
16 Correct 2560 ms 41564 KB Output is correct
17 Correct 2368 ms 73340 KB Output is correct