oj.uz

Submission #967864

# Submission time Handle Problem Language Result Execution time Memory
967864 2024-04-23T03:13:36 Z ttamx Regions (IOI09_regions) C++17
75 / 100
 2477 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[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 7 ms 18776 KB Output is correct
2 Correct 4 ms 18776 KB Output is correct
3 Correct 6 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 12 ms 18776 KB Output is correct
7 Correct 16 ms 18776 KB Output is correct
8 Correct 23 ms 19032 KB Output is correct
9 Correct 34 ms 19288 KB Output is correct
10 Correct 45 ms 19288 KB Output is correct
11 Correct 86 ms 19544 KB Output is correct
12 Correct 87 ms 19888 KB Output is correct
13 Correct 133 ms 19576 KB Output is correct
14 Correct 220 ms 20100 KB Output is correct
15 Correct 210 ms 24640 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 99196 KB Output is correct
2 Correct 719 ms 102908 KB Output is correct
3 Correct 2251 ms 40880 KB Output is correct
4 Correct 161 ms 20452 KB Output is correct
5 Correct 227 ms 21332 KB Output is correct
6 Correct 381 ms 103776 KB Output is correct
7 Correct 796 ms 100012 KB Output is correct
8 Correct 818 ms 114748 KB Output is correct
9 Correct 1757 ms 118600 KB Output is correct
10 Runtime error 366 ms 131072 KB Execution killed with signal 9
11 Runtime error 727 ms 131072 KB Execution killed with signal 9
12 Runtime error 1867 ms 131072 KB Execution killed with signal 9
13 Runtime error 1087 ms 131072 KB Execution killed with signal 9
14 Correct 1751 ms 62528 KB Output is correct
15 Correct 2477 ms 36244 KB Output is correct
16 Runtime error 396 ms 131072 KB Execution killed with signal 9
17 Correct 2190 ms 73036 KB Output is correct