oj.uz

Submission #933484

# Submission time Handle Problem Language Result Execution time Memory
933484 2024-02-25T18:07:26 Z NourWael Regions (IOI09_regions) C++17
65 / 100
 8000 ms 37412 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[region[x]][region[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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10328 KB Output isn't correct
2 Incorrect 2 ms 10328 KB Output isn't correct
3 Incorrect 3 ms 10328 KB Output isn't correct
4 Incorrect 4 ms 10328 KB Output isn't correct
5 Incorrect 5 ms 10328 KB Output isn't correct
6 Incorrect 9 ms 10328 KB Output isn't correct
7 Incorrect 13 ms 10328 KB Output isn't correct
8 Incorrect 16 ms 10328 KB Output isn't correct
9 Incorrect 26 ms 10840 KB Output isn't correct
10 Incorrect 38 ms 10584 KB Output isn't correct
11 Incorrect 51 ms 10840 KB Output isn't correct
12 Incorrect 76 ms 11348 KB Output isn't correct
13 Incorrect 77 ms 11096 KB Output isn't correct
14 Incorrect 85 ms 11356 KB Output isn't correct
15 Incorrect 115 ms 14064 KB Output isn't correct

Subtask #2
65.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 442 ms 13760 KB Output isn't correct
2 Incorrect 443 ms 13160 KB Output isn't correct
3 Incorrect 663 ms 15332 KB Output isn't correct
4 Correct 165 ms 14436 KB Output is correct
5 Correct 215 ms 16412 KB Output is correct
6 Correct 1035 ms 15636 KB Output is correct
7 Correct 1169 ms 16740 KB Output is correct
8 Correct 856 ms 22944 KB Output is correct
9 Correct 1553 ms 22848 KB Output is correct
10 Correct 3184 ms 28336 KB Output is correct
11 Correct 3266 ms 25020 KB Output is correct
12 Correct 4355 ms 22836 KB Output is correct
13 Correct 4962 ms 24212 KB Output is correct
14 Correct 6179 ms 24456 KB Output is correct
15 Correct 7192 ms 28788 KB Output is correct
16 Correct 7685 ms 37412 KB Output is correct
17 Execution timed out 8082 ms 36076 KB Time limit exceeded