oj.uz

Submission #738096

# Submission time Handle Problem Language Result Execution time Memory
738096 2023-05-08T07:20:30 Z nonono Regions (IOI09_regions) C++14
0 / 100
 644 ms 130448 KB 
#include "bits/stdc++.h"
using namespace std;

const int mxN = 2e5 + 10;
const int mxR = 25000 + 10;

int n, r, q, h[mxN];
vector<vector<int>> adj(mxN), a(mxR), b(mxR);
int pr[mxN];
unordered_map<int, int> sum[mxR];

int Time = 0, in[mxN], out[mxN], id[mxN];

void dfs(int u){
    in[u] = ++ Time;
    id[Time] = u;
    
    a[h[u]].push_back(u);
    b[h[u]].push_back(in[u]);
    
    for(int v : adj[u]){
        dfs(v);
    }
    
    out[u] = Time;
}

signed main(){

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> r >> q;
    
    for(int i = 1; i <= n; i ++){
        if(i > 1){
            int par;
            cin >> par;
            adj[par].push_back(i);
        }
        
        cin >> h[i];
    }
    
    dfs(1);
    
    for(int i = 1; i <= r; i ++){
        if((int)a[i].size() <= (int)sqrt(n)) continue ;
        for(int j = 0; j <= n; j ++) pr[j] = 0;
        
        for(int x : a[i]){
            int L = in[x];
            int R = out[x];
            
            pr[L] ++ ;
            pr[R + 1] -- ;
        }
        
        for(int j = 1; j <= n; j ++){
            pr[j] += pr[j - 1];
            sum[i][h[id[j]]] += pr[j];
        }
    }
    
    while(q --){
        int x, y;
        cin >> x >> y;
        
        if((int)a[x].size() <= (int)sqrt(n)){
            int res = 0;
            
            for(int i : a[x]){
                int L = in[i];
                int R = out[i];
                
                int l = upper_bound(b[y].begin(), b[y].end(), L) - b[y].begin();
                int r = upper_bound(b[y].begin(), b[y].end(), R) - b[y].begin();
                
                res += max(r - l, 0);
            }
            
            cout << res << "\n";
        } else {
            
            cout << sum[x][y] << "\n";
        }
        
    }
    
    return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 7504 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 7504 KB Time limit exceeded (wall clock)
3 Execution timed out 3 ms 7504 KB Time limit exceeded (wall clock)
4 Execution timed out 4 ms 7504 KB Time limit exceeded (wall clock)
5 Execution timed out 4 ms 7632 KB Time limit exceeded (wall clock)
6 Execution timed out 4 ms 7632 KB Time limit exceeded (wall clock)
7 Execution timed out 4 ms 7632 KB Time limit exceeded (wall clock)
8 Execution timed out 4 ms 7632 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 8016 KB Time limit exceeded (wall clock)
10 Execution timed out 10 ms 8196 KB Time limit exceeded (wall clock)
11 Execution timed out 8 ms 8460 KB Time limit exceeded (wall clock)
12 Execution timed out 9 ms 8988 KB Time limit exceeded (wall clock)
13 Execution timed out 11 ms 8656 KB Time limit exceeded (wall clock)
14 Execution timed out 12 ms 9424 KB Time limit exceeded (wall clock)
15 Execution timed out 15 ms 11948 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 49 ms 12880 KB Time limit exceeded (wall clock)
2 Execution timed out 39 ms 11764 KB Time limit exceeded (wall clock)
3 Execution timed out 35 ms 14652 KB Time limit exceeded (wall clock)
4 Execution timed out 14 ms 9296 KB Time limit exceeded (wall clock)
5 Execution timed out 13 ms 10928 KB Time limit exceeded (wall clock)
6 Execution timed out 104 ms 27164 KB Time limit exceeded (wall clock)
7 Execution timed out 136 ms 31652 KB Time limit exceeded (wall clock)
8 Execution timed out 302 ms 56580 KB Time limit exceeded (wall clock)
9 Execution timed out 70 ms 17608 KB Time limit exceeded (wall clock)
10 Execution timed out 644 ms 130448 KB Time limit exceeded (wall clock)
11 Execution timed out 86 ms 17560 KB Time limit exceeded (wall clock)
12 Execution timed out 100 ms 20736 KB Time limit exceeded (wall clock)
13 Execution timed out 76 ms 21036 KB Time limit exceeded (wall clock)
14 Execution timed out 241 ms 35088 KB Time limit exceeded (wall clock)
15 Execution timed out 80 ms 26300 KB Time limit exceeded (wall clock)
16 Execution timed out 92 ms 31652 KB Time limit exceeded (wall clock)
17 Execution timed out 196 ms 44504 KB Time limit exceeded (wall clock)