oj.uz

Submission #933487

# Submission time Handle Problem Language Result Execution time Memory
933487 2024-02-25T18:09:39 Z NourWael Regions (IOI09_regions) C++17
31 / 100
 3133 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;
      |          ~~~~~~~~~~~~~^~~

Subtask #1
11.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 10584 KB Time limit exceeded (wall clock)
2 Execution timed out 3 ms 10784 KB Time limit exceeded (wall clock)
3 Correct 4 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 13 ms 10584 KB Output is correct
7 Correct 14 ms 10584 KB Output is correct
8 Correct 19 ms 10584 KB Output is correct
9 Correct 31 ms 11352 KB Output is correct
10 Correct 41 ms 11096 KB Output is correct
11 Correct 66 ms 11536 KB Output is correct
12 Correct 83 ms 12096 KB Output is correct
13 Correct 108 ms 12240 KB Output is correct
14 Execution timed out 17 ms 12568 KB Time limit exceeded (wall clock)
15 Execution timed out 17 ms 16684 KB Time limit exceeded (wall clock)

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 108 ms 15900 KB Time limit exceeded (wall clock)
2 Execution timed out 72 ms 15400 KB Time limit exceeded (wall clock)
3 Execution timed out 68 ms 18568 KB Time limit exceeded (wall clock)
4 Correct 156 ms 12656 KB Output is correct
5 Correct 225 ms 15016 KB Output is correct
6 Execution timed out 326 ms 36744 KB Time limit exceeded (wall clock)
7 Execution timed out 416 ms 46132 KB Time limit exceeded (wall clock)
8 Execution timed out 989 ms 84872 KB Time limit exceeded (wall clock)
9 Correct 1513 ms 21332 KB Output is correct
10 Runtime error 1165 ms 131072 KB Execution killed with signal 9
11 Correct 3133 ms 23256 KB Output is correct
12 Execution timed out 140 ms 22396 KB Time limit exceeded (wall clock)
13 Execution timed out 115 ms 24084 KB Time limit exceeded (wall clock)
14 Execution timed out 571 ms 45832 KB Time limit exceeded (wall clock)
15 Execution timed out 126 ms 30920 KB Time limit exceeded (wall clock)
16 Execution timed out 123 ms 41532 KB Time limit exceeded (wall clock)
17 Execution timed out 545 ms 61448 KB Time limit exceeded (wall clock)