oj.uz

Submission #338616

# Submission time Handle Problem Language Result Execution time Memory
338616 2020-12-23T13:48:20 Z codebuster_10 Regions (IOI09_regions) C++17
100 / 100
 6243 ms 34296 KB 
#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 = 1e3 ;
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] ;
  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 ;
    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 ;
    }
  }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 6 ms 8556 KB Output is correct
3 Correct 8 ms 8556 KB Output is correct
4 Correct 11 ms 8556 KB Output is correct
5 Correct 11 ms 8556 KB Output is correct
6 Correct 21 ms 8832 KB Output is correct
7 Correct 22 ms 8684 KB Output is correct
8 Correct 38 ms 8684 KB Output is correct
9 Correct 49 ms 9068 KB Output is correct
10 Correct 78 ms 9068 KB Output is correct
11 Correct 142 ms 9344 KB Output is correct
12 Correct 158 ms 9836 KB Output is correct
13 Correct 205 ms 9964 KB Output is correct
14 Correct 343 ms 10220 KB Output is correct
15 Correct 300 ms 12520 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2244 ms 13292 KB Output is correct
2 Correct 2616 ms 12588 KB Output is correct
3 Correct 3063 ms 15480 KB Output is correct
4 Correct 300 ms 10320 KB Output is correct
5 Correct 399 ms 11624 KB Output is correct
6 Correct 1665 ms 11504 KB Output is correct
7 Correct 1964 ms 12468 KB Output is correct
8 Correct 1426 ms 16868 KB Output is correct
9 Correct 2511 ms 17320 KB Output is correct
10 Correct 4856 ms 21708 KB Output is correct
11 Correct 6243 ms 19680 KB Output is correct
12 Correct 1818 ms 18660 KB Output is correct
13 Correct 2522 ms 19844 KB Output is correct
14 Correct 3411 ms 20752 KB Output is correct
15 Correct 4103 ms 25140 KB Output is correct
16 Correct 3428 ms 34296 KB Output is correct
17 Correct 3521 ms 33152 KB Output is correct