oj.uz

Submission #933436

# Submission time Handle Problem Language Result Execution time Memory
933436 2024-02-25T16:32:24 Z NourWael Regions (IOI09_regions) C++17
80 / 100
 8000 ms 102096 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std; 
int const mxN = 2e5+5;
int  const mxR = 25005;
vector<int> adj [mxN];
int in[mxN], out[mxN], t, r , n, region[mxN], q, fin[505][505], cnt[505], power[mxR];
vector<pair<int,int>> reg [mxR], ori[mxR];
vector<vector<int>> seg [mxR];

void build ( int node, int l, int r , int i) {
   if(l==r-1) { seg[i][node].push_back(reg[i][l].second); return ; }
   int m = (l+r)/2;
   build(node*2+1, l, m, i), build(node*2+2, m, r, i);
   seg[i][node] = seg[i][node*2+1];
   for(auto it:seg[i][node*2+2]) seg[i][node].push_back(it);
   sort(seg[i][node].begin(),seg[i][node].end());
}

int get ( int node, int l, int r, int i, int ind , int val) {
   if(l>=ind) return 0;
   if(r<=ind) {
      int tot = seg[i][node].size();
      int smaller = lower_bound(seg[i][node].begin(), seg[i][node].end(), val ) - seg[i][node].begin();
      return tot - smaller;
   }
   int m = (l+r)/2;
   return get(node*2+1, l, m, i, ind, val) + get(node*2+2, m, r, i, ind, val);
}

void dfs ( int i, int p ) {
     t++, in[i] = t;
     for(auto it:adj[i]){
      if(it==p) continue;
      dfs(it,i);
     }
     t++, out[i] = t;
     reg[region[i]].push_back({in[i],out[i]});
}

signed main() {
   
   ios_base:: sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

   cin>>n>>r>>q>>region[1];
   for(int i=2; i<=n; i++) {
      int k, h; cin>>k>>h;
      adj[i].push_back(k), adj[k].push_back(i);
      region[i] = h;
   }

   dfs(1,0);
   for(int i=1; i<=r; i++) {
      sort(reg[i].begin(),reg[i].end());
      ori[i] = reg[i];
      int pw = (1<<(__lg(reg[i].size()-1)+1));
      power[i] = pw;
      for(int j=reg[i].size(); j<=pw; j++) reg[i].push_back({0,0});
      seg[i].resize(4*pw+5);
      build(0,0,pw, i);
   }
  for(int i=0; i<q; i++) {
      int x,y; cin>>x>>y;
      int ans = 0;
      if(ori[x].size()<=ori[y].size()) {
        for(auto it:ori[x]) {
           int ind1 = lower_bound(ori[y].begin(),ori[y].end(), it ) - ori[y].begin();
           int ind2 = lower_bound(ori[y].begin(),ori[y].end(), make_pair(it.second, 0ll) ) - ori[y].begin();
           ans += ind2-ind1;
        }
         cout<<ans<<endl; continue;
      }

      for(auto it:ori[y]){
         int ind = lower_bound(ori[x].begin(),ori[x].end(), it ) - ori[x].begin();
        ans+=get(0,0,power[x], x, ind, it.second);
      }
     cout<<ans<<endl;
   }
  return 0;

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13656 KB Output is correct
2 Correct 3 ms 13656 KB Output is correct
3 Correct 4 ms 13656 KB Output is correct
4 Correct 6 ms 13656 KB Output is correct
5 Correct 6 ms 13912 KB Output is correct
6 Correct 14 ms 13912 KB Output is correct
7 Correct 16 ms 14420 KB Output is correct
8 Correct 22 ms 14424 KB Output is correct
9 Correct 29 ms 15960 KB Output is correct
10 Correct 53 ms 17240 KB Output is correct
11 Correct 85 ms 18776 KB Output is correct
12 Correct 98 ms 21336 KB Output is correct
13 Correct 140 ms 23704 KB Output is correct
14 Correct 261 ms 26936 KB Output is correct
15 Correct 300 ms 33108 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8054 ms 43480 KB Time limit exceeded
2 Execution timed out 8037 ms 45828 KB Time limit exceeded
3 Execution timed out 8006 ms 48440 KB Time limit exceeded
4 Correct 187 ms 25944 KB Output is correct
5 Correct 257 ms 28752 KB Output is correct
6 Correct 1188 ms 30544 KB Output is correct
7 Correct 1214 ms 38300 KB Output is correct
8 Correct 914 ms 52844 KB Output is correct
9 Correct 1779 ms 78400 KB Output is correct
10 Correct 4003 ms 82948 KB Output is correct
11 Correct 4293 ms 88920 KB Output is correct
12 Correct 1375 ms 78440 KB Output is correct
13 Correct 2015 ms 79944 KB Output is correct
14 Correct 2343 ms 94888 KB Output is correct
15 Correct 3238 ms 95360 KB Output is correct
16 Correct 3086 ms 89516 KB Output is correct
17 Execution timed out 8016 ms 102096 KB Time limit exceeded