oj.uz

Submission #933489

# Submission time Handle Problem Language Result Execution time Memory
933489 2024-02-25T18:17:05 Z NourWael Regions (IOI09_regions) C++17
95 / 100
 3220 ms 131072 KB 
#include <bits/stdc++.h>
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]]--;
 
}
int 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, 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 3 ms 8024 KB Output is correct
5 Correct 5 ms 8024 KB Output is correct
6 Correct 11 ms 8280 KB Output is correct
7 Correct 15 ms 8024 KB Output is correct
8 Correct 14 ms 8280 KB Output is correct
9 Correct 25 ms 8940 KB Output is correct
10 Correct 45 ms 8536 KB Output is correct
11 Correct 62 ms 8792 KB Output is correct
12 Correct 74 ms 9780 KB Output is correct
13 Correct 124 ms 9276 KB Output is correct
14 Correct 196 ms 9608 KB Output is correct
15 Correct 207 ms 14376 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1299 ms 13180 KB Output is correct
2 Correct 1546 ms 12008 KB Output is correct
3 Correct 2085 ms 15836 KB Output is correct
4 Correct 140 ms 9768 KB Output is correct
5 Correct 200 ms 12376 KB Output is correct
6 Correct 605 ms 34220 KB Output is correct
7 Correct 1135 ms 43176 KB Output is correct
8 Correct 1619 ms 82480 KB Output is correct
9 Correct 1537 ms 17144 KB Output is correct
10 Runtime error 1179 ms 131072 KB Execution killed with signal 9
11 Correct 3220 ms 17692 KB Output is correct
12 Correct 930 ms 18364 KB Output is correct
13 Correct 1328 ms 20112 KB Output is correct
14 Correct 1901 ms 41200 KB Output is correct
15 Correct 2035 ms 27484 KB Output is correct
16 Correct 2116 ms 40472 KB Output is correct
17 Correct 2392 ms 59948 KB Output is correct