oj.uz

Submission #738056

# Submission time Handle Problem Language Result Execution time Memory
738056 2023-05-08T06:38:39 Z nonono Regions (IOI09_regions) C++17
0 / 100
 619 ms 130440 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".in", "r")){
        freopen(name".in", "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".in", "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 4 ms 7596 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 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 6 ms 8144 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 8144 KB Time limit exceeded (wall clock)
11 Execution timed out 7 ms 8400 KB Time limit exceeded (wall clock)
12 Execution timed out 8 ms 8912 KB Time limit exceeded (wall clock)
13 Execution timed out 11 ms 8656 KB Time limit exceeded (wall clock)
14 Execution timed out 13 ms 9424 KB Time limit exceeded (wall clock)
15 Execution timed out 16 ms 11984 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 48 ms 12856 KB Time limit exceeded (wall clock)
2 Execution timed out 40 ms 11728 KB Time limit exceeded (wall clock)
3 Execution timed out 39 ms 14752 KB Time limit exceeded (wall clock)
4 Execution timed out 13 ms 9384 KB Time limit exceeded (wall clock)
5 Execution timed out 15 ms 10960 KB Time limit exceeded (wall clock)
6 Execution timed out 107 ms 27144 KB Time limit exceeded (wall clock)
7 Execution timed out 146 ms 31620 KB Time limit exceeded (wall clock)
8 Execution timed out 299 ms 56624 KB Time limit exceeded (wall clock)
9 Execution timed out 63 ms 17608 KB Time limit exceeded (wall clock)
10 Execution timed out 619 ms 130440 KB Time limit exceeded (wall clock)
11 Execution timed out 99 ms 17528 KB Time limit exceeded (wall clock)
12 Execution timed out 105 ms 20800 KB Time limit exceeded (wall clock)
13 Execution timed out 86 ms 20980 KB Time limit exceeded (wall clock)
14 Execution timed out 239 ms 35040 KB Time limit exceeded (wall clock)
15 Execution timed out 86 ms 26256 KB Time limit exceeded (wall clock)
16 Execution timed out 91 ms 31720 KB Time limit exceeded (wall clock)
17 Execution timed out 224 ms 44488 KB Time limit exceeded (wall clock)