oj.uz

Submission #967870

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

using namespace std;

const int N=2e5+5;
const int K=405;
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 3 ms 16728 KB Output is correct
2 Correct 4 ms 16728 KB Output is correct
3 Correct 5 ms 16728 KB Output is correct
4 Correct 6 ms 16728 KB Output is correct
5 Correct 7 ms 16728 KB Output is correct
6 Correct 11 ms 16728 KB Output is correct
7 Correct 15 ms 16728 KB Output is correct
8 Correct 20 ms 16984 KB Output is correct
9 Correct 25 ms 17240 KB Output is correct
10 Correct 61 ms 17240 KB Output is correct
11 Correct 88 ms 17496 KB Output is correct
12 Correct 90 ms 18028 KB Output is correct
13 Correct 122 ms 17860 KB Output is correct
14 Correct 227 ms 18364 KB Output is correct
15 Correct 212 ms 20056 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1429 ms 53924 KB Output is correct
2 Correct 1634 ms 42468 KB Output is correct
3 Correct 2252 ms 41232 KB Output is correct
4 Correct 168 ms 18520 KB Output is correct
5 Correct 243 ms 19544 KB Output is correct
6 Correct 403 ms 110040 KB Output is correct
7 Correct 1060 ms 63504 KB Output is correct
8 Correct 807 ms 122984 KB Output is correct
9 Correct 1845 ms 25064 KB Output is correct
10 Correct 2400 ms 130996 KB Output is correct
11 Correct 3195 ms 24744 KB Output is correct
12 Correct 1041 ms 32396 KB Output is correct
13 Correct 1368 ms 32580 KB Output is correct
14 Correct 1779 ms 63144 KB Output is correct
15 Correct 2430 ms 36744 KB Output is correct
16 Correct 2194 ms 42064 KB Output is correct
17 Correct 2291 ms 73832 KB Output is correct