oj.uz

Submission #933382

# Submission time Handle Problem Language Result Execution time Memory
933382 2024-02-25T15:23:18 Z NourWael Regions (IOI09_regions) C++17
95 / 100
 8000 ms 37392 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];
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]});
}

void dfs2 ( int i, int p ) {
  for(int j=1; j<=r; j++) {
      if(region[i]==j) continue;
      fin[j][region[i]] += cnt[j];
     }
     cnt[region[i]]++;
     for(auto it:adj[i]){
      if(it==p) continue;
      dfs2(it,i);
     }
     cnt[region[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;
   }

   if(r>500) dfs(1,0);
   else dfs2(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;
      if(r<=500) { cout<<fin[x][y]<<endl; continue; }
      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 4 ms 10328 KB Output is correct
3 Correct 3 ms 10328 KB Output is correct
4 Correct 5 ms 10328 KB Output is correct
5 Correct 5 ms 10328 KB Output is correct
6 Correct 12 ms 10328 KB Output is correct
7 Correct 17 ms 10328 KB Output is correct
8 Correct 15 ms 10324 KB Output is correct
9 Correct 20 ms 10840 KB Output is correct
10 Correct 46 ms 10584 KB Output is correct
11 Correct 50 ms 10840 KB Output is correct
12 Correct 76 ms 11144 KB Output is correct
13 Correct 81 ms 11096 KB Output is correct
14 Correct 95 ms 11352 KB Output is correct
15 Correct 95 ms 13912 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 13636 KB Output is correct
2 Correct 517 ms 13464 KB Output is correct
3 Correct 798 ms 15152 KB Output is correct
4 Correct 145 ms 14432 KB Output is correct
5 Correct 212 ms 16412 KB Output is correct
6 Correct 986 ms 15608 KB Output is correct
7 Correct 1138 ms 16800 KB Output is correct
8 Correct 749 ms 22936 KB Output is correct
9 Correct 1519 ms 22848 KB Output is correct
10 Correct 3102 ms 28432 KB Output is correct
11 Correct 3037 ms 25216 KB Output is correct
12 Correct 3969 ms 22652 KB Output is correct
13 Correct 4596 ms 24108 KB Output is correct
14 Correct 5754 ms 24220 KB Output is correct
15 Correct 6557 ms 28676 KB Output is correct
16 Correct 7497 ms 37392 KB Output is correct
17 Execution timed out 8038 ms 35812 KB Time limit exceeded