oj.uz

Submission #967859

# Submission time Handle Problem Language Result Execution time Memory
967859 2024-04-23T03:04:54 Z ttamx Regions (IOI09_regions) C++17
55 / 100
 3578 ms 71800 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[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,cnt);
        }
    }
    while(q--){
        int r1,r2;
        cin >> r1 >> r2;
        if(comp[r1].size()>K)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 5 ms 16728 KB Output is correct
5 Correct 8 ms 16728 KB Output is correct
6 Correct 16 ms 16728 KB Output is correct
7 Correct 18 ms 16728 KB Output is correct
8 Correct 17 ms 16984 KB Output is correct
9 Correct 26 ms 17240 KB Output is correct
10 Correct 45 ms 17488 KB Output is correct
11 Correct 83 ms 17484 KB Output is correct
12 Correct 83 ms 18008 KB Output is correct
13 Correct 117 ms 17672 KB Output is correct
14 Correct 206 ms 18228 KB Output is correct
15 Correct 201 ms 20180 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1510 ms 39560 KB Output isn't correct
2 Incorrect 1705 ms 40420 KB Output isn't correct
3 Incorrect 2394 ms 39136 KB Output isn't correct
4 Correct 180 ms 18264 KB Output is correct
5 Correct 238 ms 19392 KB Output is correct
6 Correct 1143 ms 19340 KB Output is correct
7 Correct 1396 ms 20180 KB Output is correct
8 Correct 1002 ms 24080 KB Output is correct
9 Correct 1787 ms 24860 KB Output is correct
10 Correct 3578 ms 28544 KB Output is correct
11 Correct 3365 ms 24736 KB Output is correct
12 Incorrect 978 ms 30340 KB Output isn't correct
13 Incorrect 1408 ms 30528 KB Output isn't correct
14 Incorrect 1789 ms 61140 KB Output isn't correct
15 Incorrect 2405 ms 34708 KB Output isn't correct
16 Incorrect 2248 ms 39932 KB Output isn't correct
17 Incorrect 2237 ms 71800 KB Output isn't correct