oj.uz

Submission #967869

# Submission time Handle Problem Language Result Execution time Memory
967869 2024-04-23T03:21:44 Z ttamx Regions (IOI09_regions) C++17
95 / 100
 3338 ms 131072 KB 
#include<bits/stdc++.h>
#define all(x) begin(x),end(x)

using namespace std;

const int N=2e5+5;
const int K=400;
const int M=505;

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 3 ms 16728 KB Output is correct
3 Correct 8 ms 16728 KB Output is correct
4 Correct 6 ms 16728 KB Output is correct
5 Correct 6 ms 16840 KB Output is correct
6 Correct 11 ms 16728 KB Output is correct
7 Correct 16 ms 16728 KB Output is correct
8 Correct 17 ms 16984 KB Output is correct
9 Correct 24 ms 17240 KB Output is correct
10 Correct 61 ms 17240 KB Output is correct
11 Correct 73 ms 17496 KB Output is correct
12 Correct 94 ms 18008 KB Output is correct
13 Correct 119 ms 17752 KB Output is correct
14 Correct 187 ms 18316 KB Output is correct
15 Correct 209 ms 20016 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1436 ms 54028 KB Output is correct
2 Correct 1644 ms 42464 KB Output is correct
3 Correct 2254 ms 41016 KB Output is correct
4 Correct 165 ms 18264 KB Output is correct
5 Correct 273 ms 19592 KB Output is correct
6 Correct 413 ms 101952 KB Output is correct
7 Correct 1087 ms 65944 KB Output is correct
8 Correct 808 ms 120948 KB Output is correct
9 Correct 1749 ms 24964 KB Output is correct
10 Runtime error 258 ms 131072 KB Execution killed with signal 9
11 Correct 3338 ms 24736 KB Output is correct
12 Correct 1036 ms 32384 KB Output is correct
13 Correct 1393 ms 32584 KB Output is correct
14 Correct 1716 ms 63220 KB Output is correct
15 Correct 2489 ms 36744 KB Output is correct
16 Correct 2176 ms 41872 KB Output is correct
17 Correct 2235 ms 73664 KB Output is correct