oj.uz

Submission #933492

# Submission time Handle Problem Language Result Execution time Memory
933492 2024-02-25T18:26:27 Z NourWael Regions (IOI09_regions) C++17
100 / 100
 3431 ms 33644 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, ind[mxR];
int fin [500][mxR];
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[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);
   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) { ind[i] = pre.size(); 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[ind[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) { ind[i] = pre.size(); 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[ind[x]][y]<<endl; continue; }
      |          ~~~~~~~~~~~~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 2 ms 9816 KB Output is correct
3 Correct 5 ms 9816 KB Output is correct
4 Correct 4 ms 9816 KB Output is correct
5 Correct 5 ms 9816 KB Output is correct
6 Correct 10 ms 10072 KB Output is correct
7 Correct 15 ms 10072 KB Output is correct
8 Correct 18 ms 10072 KB Output is correct
9 Correct 28 ms 10616 KB Output is correct
10 Correct 50 ms 10300 KB Output is correct
11 Correct 71 ms 10584 KB Output is correct
12 Correct 89 ms 11244 KB Output is correct
13 Correct 110 ms 11096 KB Output is correct
14 Correct 193 ms 11436 KB Output is correct
15 Correct 184 ms 14956 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1238 ms 16432 KB Output is correct
2 Correct 1550 ms 13688 KB Output is correct
3 Correct 2009 ms 16552 KB Output is correct
4 Correct 159 ms 11800 KB Output is correct
5 Correct 242 ms 13428 KB Output is correct
6 Correct 284 ms 18856 KB Output is correct
7 Correct 769 ms 17444 KB Output is correct
8 Correct 621 ms 27756 KB Output is correct
9 Correct 1487 ms 18388 KB Output is correct
10 Correct 1992 ms 32600 KB Output is correct
11 Correct 3431 ms 19428 KB Output is correct
12 Correct 856 ms 18352 KB Output is correct
13 Correct 1282 ms 19624 KB Output is correct
14 Correct 1368 ms 21340 KB Output is correct
15 Correct 2077 ms 24076 KB Output is correct
16 Correct 1994 ms 33192 KB Output is correct
17 Correct 1938 ms 33644 KB Output is correct