oj.uz

Submission #967858

# Submission time Handle Problem Language Result Execution time Memory
967858 2024-04-23T03:03:13 Z ttamx Regions (IOI09_regions) C++17
24 / 100
 2561 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=200;
const int M=1005;

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
14.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18776 KB Output is correct
2 Correct 5 ms 18776 KB Output is correct
3 Correct 5 ms 18776 KB Output is correct
4 Correct 5 ms 18776 KB Output is correct
5 Correct 8 ms 18776 KB Output is correct
6 Correct 11 ms 18776 KB Output is correct
7 Correct 19 ms 18776 KB Output is correct
8 Correct 19 ms 19032 KB Output is correct
9 Correct 30 ms 19288 KB Output is correct
10 Correct 42 ms 19288 KB Output is correct
11 Correct 85 ms 19580 KB Output is correct
12 Correct 112 ms 20008 KB Output is correct
13 Correct 130 ms 19544 KB Output is correct
14 Correct 207 ms 20152 KB Output is correct
15 Incorrect 214 ms 24572 KB Output isn't correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1055 ms 115540 KB Output isn't correct
2 Incorrect 782 ms 114884 KB Output isn't correct
3 Incorrect 2286 ms 40688 KB Output isn't correct
4 Correct 174 ms 20324 KB Output is correct
5 Correct 240 ms 21404 KB Output is correct
6 Incorrect 429 ms 115616 KB Output isn't correct
7 Incorrect 859 ms 100664 KB Output isn't correct
8 Incorrect 747 ms 120912 KB Output isn't correct
9 Incorrect 1722 ms 122276 KB Output isn't correct
10 Runtime error 302 ms 131072 KB Execution killed with signal 9
11 Runtime error 666 ms 131072 KB Execution killed with signal 9
12 Runtime error 1156 ms 131072 KB Execution killed with signal 9
13 Runtime error 724 ms 131072 KB Execution killed with signal 9
14 Incorrect 1705 ms 62536 KB Output isn't correct
15 Incorrect 2561 ms 36128 KB Output isn't correct
16 Runtime error 313 ms 131072 KB Execution killed with signal 9
17 Incorrect 2294 ms 73804 KB Output isn't correct