oj.uz

Submission #967862

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

using namespace std;

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

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 5 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 7 ms 16728 KB Output is correct
6 Correct 11 ms 16728 KB Output is correct
7 Correct 14 ms 16728 KB Output is correct
8 Correct 18 ms 16984 KB Output is correct
9 Correct 24 ms 17240 KB Output is correct
10 Correct 45 ms 17240 KB Output is correct
11 Correct 70 ms 17496 KB Output is correct
12 Correct 87 ms 17976 KB Output is correct
13 Correct 127 ms 17752 KB Output is correct
14 Correct 199 ms 18160 KB Output is correct
15 Correct 200 ms 20184 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1457 ms 39560 KB Output is correct
2 Correct 1684 ms 40464 KB Output is correct
3 Correct 2260 ms 39308 KB Output is correct
4 Correct 166 ms 18264 KB Output is correct
5 Correct 236 ms 19544 KB Output is correct
6 Correct 1076 ms 19384 KB Output is correct
7 Correct 1353 ms 20260 KB Output is correct
8 Correct 972 ms 23972 KB Output is correct
9 Correct 1722 ms 25276 KB Output is correct
10 Correct 3613 ms 28664 KB Output is correct
11 Correct 3395 ms 24736 KB Output is correct
12 Correct 975 ms 30340 KB Output is correct
13 Correct 1493 ms 30532 KB Output is correct
14 Correct 1806 ms 61140 KB Output is correct
15 Correct 2428 ms 34696 KB Output is correct
16 Correct 2251 ms 39944 KB Output is correct
17 Correct 2139 ms 71660 KB Output is correct