oj.uz

Submission #967860

# Submission time Handle Problem Language Result Execution time Memory
967860 2024-04-23T03:09:05 Z ttamx Regions (IOI09_regions) C++17
55 / 100
 3435 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){
    dp[i][a[u]]+=c;
    if(a[u]==i)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,cnt);
        }
    }
    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 3 ms 16728 KB Output is correct
3 Correct 4 ms 16728 KB Output is correct
4 Correct 6 ms 16724 KB Output is correct
5 Correct 6 ms 16728 KB Output is correct
6 Correct 12 ms 16728 KB Output is correct
7 Correct 16 ms 16728 KB Output is correct
8 Correct 19 ms 16984 KB Output is correct
9 Correct 31 ms 17236 KB Output is correct
10 Correct 52 ms 17400 KB Output is correct
11 Correct 94 ms 17496 KB Output is correct
12 Correct 81 ms 18024 KB Output is correct
13 Correct 116 ms 17752 KB Output is correct
14 Correct 212 ms 18364 KB Output is correct
15 Correct 230 ms 20068 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1449 ms 39568 KB Output isn't correct
2 Incorrect 1676 ms 40416 KB Output isn't correct
3 Incorrect 2225 ms 39080 KB Output isn't correct
4 Correct 160 ms 18264 KB Output is correct
5 Correct 238 ms 19544 KB Output is correct
6 Correct 1056 ms 19384 KB Output is correct
7 Correct 1300 ms 20148 KB Output is correct
8 Correct 978 ms 24108 KB Output is correct
9 Correct 1748 ms 24892 KB Output is correct
10 Correct 3435 ms 28660 KB Output is correct
11 Correct 3337 ms 24732 KB Output is correct
12 Incorrect 975 ms 30336 KB Output isn't correct
13 Incorrect 1375 ms 30524 KB Output isn't correct
14 Incorrect 1644 ms 61140 KB Output isn't correct
15 Incorrect 2407 ms 34704 KB Output isn't correct
16 Incorrect 2105 ms 40020 KB Output isn't correct
17 Incorrect 2118 ms 71660 KB Output isn't correct