oj.uz

Submission #967872

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

using namespace std;

const int N=2e5+5;
const int K=450;
const int M=450;

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 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 4 ms 16728 KB Output is correct
4 Correct 6 ms 16728 KB Output is correct
5 Correct 6 ms 16728 KB Output is correct
6 Correct 12 ms 16728 KB Output is correct
7 Correct 19 ms 16840 KB Output is correct
8 Correct 22 ms 16984 KB Output is correct
9 Correct 29 ms 17100 KB Output is correct
10 Correct 48 ms 17496 KB Output is correct
11 Correct 82 ms 17592 KB Output is correct
12 Correct 92 ms 18008 KB Output is correct
13 Correct 121 ms 17748 KB Output is correct
14 Correct 201 ms 18196 KB Output is correct
15 Correct 219 ms 20104 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1428 ms 47768 KB Output is correct
2 Correct 1704 ms 42456 KB Output is correct
3 Correct 2261 ms 41164 KB Output is correct
4 Correct 167 ms 18272 KB Output is correct
5 Correct 221 ms 19524 KB Output is correct
6 Correct 400 ms 113900 KB Output is correct
7 Correct 1177 ms 43032 KB Output is correct
8 Correct 719 ms 117300 KB Output is correct
9 Correct 1763 ms 25004 KB Output is correct
10 Correct 2894 ms 114212 KB Output is correct
11 Correct 3402 ms 24732 KB Output is correct
12 Correct 999 ms 32376 KB Output is correct
13 Correct 1415 ms 32592 KB Output is correct
14 Correct 1659 ms 63140 KB Output is correct
15 Correct 2399 ms 36748 KB Output is correct
16 Correct 2334 ms 42092 KB Output is correct
17 Correct 2236 ms 73652 KB Output is correct