oj.uz

Submission #933488

# Submission time Handle Problem Language Result Execution time Memory
933488 2024-02-25T18:14:21 Z NourWael Regions (IOI09_regions) C++17
95 / 100
 3219 ms 131072 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, cnt[mxR], c;
map<pair<int,int>,int> fin;
vector<pair<int,int>> reg [mxR];
vector<int> pre;
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=0; j<pre.size(); j++) {
        if(region[i]==pre[j]) continue;
        fin[{pre[j],region[i]}] += cnt[pre[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];
   c = sqrt(n); c++;
   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());
      if(reg[i].size()>=c) pre.push_back(i);
   }
   dfs2(1,0);
   for(int i=0; i<q; i++) {
      int x,y; cin>>x>>y;
      int ans = 0;
      if(reg[x].size()>=c) { 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;
 
}

Compilation message

regions.cpp: In function 'void dfs2(long long int, long long int)':
regions.cpp:22:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |      for(int j=0; j<pre.size(); j++) {
      |                   ~^~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:51:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   51 |       if(reg[i].size()>=c) pre.push_back(i);
      |          ~~~~~~~~~~~~~^~~
regions.cpp:57:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   57 |       if(reg[x].size()>=c) { cout<<fin[{x,y}]<<endl; continue; }
      |          ~~~~~~~~~~~~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 2 ms 10584 KB Output is correct
3 Correct 3 ms 10584 KB Output is correct
4 Correct 5 ms 10584 KB Output is correct
5 Correct 5 ms 10584 KB Output is correct
6 Correct 11 ms 10584 KB Output is correct
7 Correct 24 ms 10836 KB Output is correct
8 Correct 15 ms 10584 KB Output is correct
9 Correct 23 ms 11352 KB Output is correct
10 Correct 44 ms 11096 KB Output is correct
11 Correct 70 ms 11552 KB Output is correct
12 Correct 82 ms 12120 KB Output is correct
13 Correct 92 ms 12256 KB Output is correct
14 Correct 180 ms 12564 KB Output is correct
15 Correct 212 ms 18124 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1366 ms 16596 KB Output is correct
2 Correct 1592 ms 15548 KB Output is correct
3 Correct 2078 ms 19664 KB Output is correct
4 Correct 165 ms 12708 KB Output is correct
5 Correct 220 ms 16032 KB Output is correct
6 Correct 668 ms 37780 KB Output is correct
7 Correct 1228 ms 46704 KB Output is correct
8 Correct 1724 ms 86936 KB Output is correct
9 Correct 1503 ms 21916 KB Output is correct
10 Runtime error 1189 ms 131072 KB Execution killed with signal 9
11 Correct 3219 ms 23352 KB Output is correct
12 Correct 896 ms 22672 KB Output is correct
13 Correct 1294 ms 25276 KB Output is correct
14 Correct 1987 ms 46036 KB Output is correct
15 Correct 2099 ms 32936 KB Output is correct
16 Correct 2021 ms 47556 KB Output is correct
17 Correct 2519 ms 66872 KB Output is correct