oj.uz

Submission #738058

# Submission time Handle Problem Language Result Execution time Memory
738058 2023-05-08T06:43:10 Z nonono Regions (IOI09_regions) C++17
0 / 100
 634 ms 130552 KB 
#include "bits/stdc++.h"
using namespace std;

const int mxN = 2e5 + 10;
const int mxR = 25e3 + 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(){

    #define name "regions"
    if(fopen(name".inp", "r")){
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    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;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5 ms 7504 KB Time limit exceeded (wall clock)
2 Execution timed out 4 ms 7504 KB Time limit exceeded (wall clock)
3 Execution timed out 4 ms 7580 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 7668 KB Time limit exceeded (wall clock)
9 Execution timed out 5 ms 8144 KB Time limit exceeded (wall clock)
10 Execution timed out 7 ms 8144 KB Time limit exceeded (wall clock)
11 Execution timed out 9 ms 8392 KB Time limit exceeded (wall clock)
12 Execution timed out 14 ms 8912 KB Time limit exceeded (wall clock)
13 Execution timed out 12 ms 8656 KB Time limit exceeded (wall clock)
14 Execution timed out 18 ms 9456 KB Time limit exceeded (wall clock)
15 Execution timed out 15 ms 12024 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 46 ms 12876 KB Time limit exceeded (wall clock)
2 Execution timed out 42 ms 11656 KB Time limit exceeded (wall clock)
3 Execution timed out 38 ms 14664 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 10960 KB Time limit exceeded (wall clock)
6 Execution timed out 109 ms 27188 KB Time limit exceeded (wall clock)
7 Execution timed out 143 ms 31656 KB Time limit exceeded (wall clock)
8 Execution timed out 295 ms 56584 KB Time limit exceeded (wall clock)
9 Execution timed out 59 ms 17556 KB Time limit exceeded (wall clock)
10 Execution timed out 634 ms 130552 KB Time limit exceeded (wall clock)
11 Execution timed out 83 ms 17520 KB Time limit exceeded (wall clock)
12 Execution timed out 95 ms 20760 KB Time limit exceeded (wall clock)
13 Execution timed out 88 ms 20948 KB Time limit exceeded (wall clock)
14 Execution timed out 224 ms 35092 KB Time limit exceeded (wall clock)
15 Execution timed out 93 ms 26288 KB Time limit exceeded (wall clock)
16 Execution timed out 84 ms 31672 KB Time limit exceeded (wall clock)
17 Execution timed out 190 ms 44616 KB Time limit exceeded (wall clock)