oj.uz

Submission #933479

# Submission time Handle Problem Language Result Execution time Memory
933479 2024-02-25T17:58:10 Z NourWael Regions (IOI09_regions) C++17
95 / 100
 3020 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);
   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:52: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]
   52 |       if(reg[i].size()>=c) pre.push_back(i);
      |          ~~~~~~~~~~~~~^~~
regions.cpp:58: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]
   58 |       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 3 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 4 ms 10584 KB Output is correct
5 Correct 5 ms 10584 KB Output is correct
6 Correct 10 ms 10584 KB Output is correct
7 Correct 15 ms 10584 KB Output is correct
8 Correct 17 ms 10584 KB Output is correct
9 Correct 25 ms 11352 KB Output is correct
10 Correct 41 ms 11096 KB Output is correct
11 Correct 66 ms 11556 KB Output is correct
12 Correct 82 ms 12096 KB Output is correct
13 Correct 111 ms 12256 KB Output is correct
14 Correct 187 ms 12576 KB Output is correct
15 Correct 203 ms 18008 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1323 ms 16608 KB Output is correct
2 Correct 1554 ms 15552 KB Output is correct
3 Correct 2054 ms 19652 KB Output is correct
4 Correct 151 ms 12708 KB Output is correct
5 Correct 214 ms 15788 KB Output is correct
6 Correct 664 ms 37316 KB Output is correct
7 Correct 1147 ms 46576 KB Output is correct
8 Correct 1755 ms 86800 KB Output is correct
9 Correct 1487 ms 21980 KB Output is correct
10 Runtime error 1119 ms 131072 KB Execution killed with signal 9
11 Correct 3020 ms 23352 KB Output is correct
12 Correct 874 ms 22672 KB Output is correct
13 Correct 1256 ms 24944 KB Output is correct
14 Correct 1985 ms 46048 KB Output is correct
15 Correct 2019 ms 32916 KB Output is correct
16 Correct 2087 ms 47556 KB Output is correct
17 Correct 2467 ms 66956 KB Output is correct