Submission #338614

#	Time	Username	Problem	Language	Result	Execution time	Memory
338614		codebuster_10	Regions (IOI09_regions)	C++17	100 / 100	6344 ms	34276 KiB

regions

#include <bits/stdc++.h>

using namespace std ;

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
//#define int long long 
#define ld long double
#define f(i,a,b) for(int i=a; i<b; ++i)

//#define endl '\n'
#define debug cout<<"\n========================================\n";
#define err1(a) cout<<#a<<" "<<a<<endl;
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl;
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl;
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl;

#define PQ priority_queue
#define LB lower_bound  
#define UB upper_bound
#define fr first
#define sc second

#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define show(a) {for(auto xyz:a)cout<<xyz<<" ";cout<<endl;}
#define sz(x) (int)(x).size()

const int C = 2e3 ;
const int MAXN = 2e5 + 7, MAXR = 25007 ;
vector<int> g[MAXN], st(MAXN), en(MAXN), euler, home[MAXR], h(MAXN), HomeEuler[MAXR] ;
int timer ;
void dfs(int i, int p){
  euler.push_back(i) ;
  st[i] = timer++ ;
  for(auto j:g[i]) if(j!=p){
    dfs(j, i);
  }
  en[i] = timer - 1 ;
}
void dfs2(int i,int p,int Node,int cnt,vector<int> &ans){
  if( h[i] == Node ) {
    cnt++ ;
  }else{
    ans[h[i]] += cnt ;
  }
  for(auto j:g[i]) if(j!=p){
    dfs2(j,i,Node,cnt,ans) ;
  }
  if( h[i] == Node )  cnt-- ;
}
signed main(){
  fastio ;
  int N, R, Q; cin >> N >> R >> Q ;
  f(i, 0, N){
    if(i == 0){
      int x ; cin >> x ; --x;
      home[x].push_back(i) ;
      h[i] = x ;
      continue ;
    }
    int x, y; cin >> x >> y ; --x,--y;
    g[i].push_back(x) ;
    g[x].push_back(i) ;
    home[y].push_back(i) ;
    h[i] = y ;
  }
  dfs(0, 0) ;
  f(i,0,N){
    euler[i] = h[euler[i]] ;
    HomeEuler[euler[i]].push_back(i) ;
  }
  auto get=[&](int i,int x){
    return UB(all(HomeEuler[x]),i) - HomeEuler[x].begin() ; 
  };
  vector<int> ans[R] ;
  int cnt = 0 ;
  f(i,0,R){
    if(sz(home[i]) >= C){
      vector<int> temp(R, 0) ;
      dfs2(0, 0, i, 0, temp) ;
      ans[i] = temp ;
    }
  }
  while(Q--){
    int r1, r2 ; cin >> r1 >> r2 ; --r1, --r2 ; cout << endl ;
    if( sz(home[r1]) >= C){
      cout << ans[r1][r2] << endl ;
    }else{
      int res = 0 ;
      for(auto i:home[r1]){
        res += get(en[i], r2) - get(st[i], r2) ;
      }
      cout << res << endl ;
    }
  }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:76:7: warning: unused variable 'cnt' [-Wunused-variable]
   76 |   int cnt = 0 ;
      |       ^~~

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85