oj.uz

Submission #933491

# Submission time Handle Problem Language Result Execution time Memory
933491 2024-02-25T18:21:24 Z NourWael Regions (IOI09_regions) C++17
95 / 100
 3136 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std; 
int const mxN = 2e5+1;
int  const mxR = 25001;
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]]--;
 
}
int main() {
   
   ios_base:: sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);
 
   cin>>n>>r>>q>>region[1];
   c = sqrt(n); c+=2;
   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, 0) ) - reg[y].begin();
         ans += ind2-ind1;
      }
      cout<<ans<<endl;
   }
  return 0;
 
}

Compilation message

regions.cpp: In function 'void dfs2(int, int)':
regions.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |      for(int j=0; j<pre.size(); j++) {
      |                   ~^~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:50:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |       if(reg[i].size()>=c) pre.push_back(i);
      |          ~~~~~~~~~~~~~^~~
regions.cpp:56:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |       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 8024 KB Output is correct
2 Correct 2 ms 8024 KB Output is correct
3 Correct 3 ms 8024 KB Output is correct
4 Correct 4 ms 8024 KB Output is correct
5 Correct 7 ms 8024 KB Output is correct
6 Correct 12 ms 8280 KB Output is correct
7 Correct 18 ms 8024 KB Output is correct
8 Correct 14 ms 8280 KB Output is correct
9 Correct 24 ms 8936 KB Output is correct
10 Correct 40 ms 8536 KB Output is correct
11 Correct 72 ms 8792 KB Output is correct
12 Correct 105 ms 9560 KB Output is correct
13 Correct 127 ms 9180 KB Output is correct
14 Correct 222 ms 9608 KB Output is correct
15 Correct 201 ms 14376 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1311 ms 13176 KB Output is correct
2 Correct 1502 ms 11996 KB Output is correct
3 Correct 1983 ms 15828 KB Output is correct
4 Correct 159 ms 9768 KB Output is correct
5 Correct 227 ms 12332 KB Output is correct
6 Correct 646 ms 33964 KB Output is correct
7 Correct 1116 ms 43224 KB Output is correct
8 Correct 1630 ms 82424 KB Output is correct
9 Correct 1690 ms 17136 KB Output is correct
10 Runtime error 1166 ms 131072 KB Execution killed with signal 9
11 Correct 3136 ms 17696 KB Output is correct
12 Correct 1010 ms 18360 KB Output is correct
13 Correct 1299 ms 20104 KB Output is correct
14 Correct 2009 ms 41200 KB Output is correct
15 Correct 2136 ms 27488 KB Output is correct
16 Correct 1988 ms 40436 KB Output is correct
17 Correct 2411 ms 59884 KB Output is correct