oj.uz

Submission #933380

# Submission time Handle Problem Language Result Execution time Memory
933380 2024-02-25T15:17:32 Z NourWael Regions (IOI09_regions) C++17
80 / 100
 8000 ms 35400 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;
vector<pair<int,int>> reg [mxR];

void dfs ( int i, int p ) {
     in[i] = t;
     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());

   for(int i=0; i<q; i++) {
      int x,y; cin>>x>>y;
      int ans = 0;
      for(auto it:reg[x]) {
         int ind1 = lower_bound(reg[y].begin(),reg[y].end(), it ) - reg[y].begin();
         int ind2 = lower_bound(reg[y].begin(),reg[y].end(), make_pair(it.second, 0ll) ) - reg[y].begin();
         ans += ind2-ind1;
      }
      cout<<ans<<endl;
   }
  return 0;

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10328 KB Output is correct
2 Correct 2 ms 10328 KB Output is correct
3 Correct 3 ms 10328 KB Output is correct
4 Correct 4 ms 10328 KB Output is correct
5 Correct 5 ms 10328 KB Output is correct
6 Correct 9 ms 10328 KB Output is correct
7 Correct 17 ms 10328 KB Output is correct
8 Correct 18 ms 10328 KB Output is correct
9 Correct 30 ms 11096 KB Output is correct
10 Correct 43 ms 10840 KB Output is correct
11 Correct 75 ms 11328 KB Output is correct
12 Correct 84 ms 11696 KB Output is correct
13 Correct 107 ms 12048 KB Output is correct
14 Correct 195 ms 12356 KB Output is correct
15 Correct 187 ms 15936 KB Output is correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8071 ms 15796 KB Time limit exceeded
2 Execution timed out 8012 ms 15112 KB Time limit exceeded
3 Execution timed out 8074 ms 17844 KB Time limit exceeded
4 Correct 172 ms 12448 KB Output is correct
5 Correct 214 ms 14412 KB Output is correct
6 Correct 1052 ms 13584 KB Output is correct
7 Correct 1229 ms 14668 KB Output is correct
8 Correct 875 ms 20924 KB Output is correct
9 Correct 1591 ms 20848 KB Output is correct
10 Correct 3189 ms 26288 KB Output is correct
11 Correct 3313 ms 23084 KB Output is correct
12 Correct 4155 ms 20656 KB Output is correct
13 Correct 4874 ms 22112 KB Output is correct
14 Correct 6087 ms 22032 KB Output is correct
15 Correct 6596 ms 26632 KB Output is correct
16 Correct 6999 ms 35400 KB Output is correct
17 Execution timed out 8013 ms 33976 KB Time limit exceeded