oj.uz

Submission #338614

# Submission time Handle Problem Language Result Execution time Memory
338614 2020-12-23T13:45:26 Z codebuster_10 Regions (IOI09_regions) C++17
100 / 100
 6344 ms 34276 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 = 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

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

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8556 KB Output is correct
2 Correct 7 ms 8556 KB Output is correct
3 Correct 8 ms 8556 KB Output is correct
4 Correct 12 ms 8556 KB Output is correct
5 Correct 16 ms 8556 KB Output is correct
6 Correct 30 ms 8684 KB Output is correct
7 Correct 40 ms 8684 KB Output is correct
8 Correct 48 ms 8812 KB Output is correct
9 Correct 63 ms 9068 KB Output is correct
10 Correct 98 ms 9196 KB Output is correct
11 Correct 160 ms 9324 KB Output is correct
12 Correct 159 ms 9836 KB Output is correct
13 Correct 202 ms 9836 KB Output is correct
14 Correct 426 ms 10220 KB Output is correct
15 Correct 322 ms 12520 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2535 ms 13260 KB Output is correct
2 Correct 3371 ms 12588 KB Output is correct
3 Correct 3861 ms 15480 KB Output is correct
4 Correct 289 ms 10320 KB Output is correct
5 Correct 401 ms 11624 KB Output is correct
6 Correct 1839 ms 11468 KB Output is correct
7 Correct 2239 ms 12468 KB Output is correct
8 Correct 1830 ms 16816 KB Output is correct
9 Correct 3231 ms 17348 KB Output is correct
10 Correct 5615 ms 21728 KB Output is correct
11 Correct 6344 ms 19792 KB Output is correct
12 Correct 1931 ms 18660 KB Output is correct
13 Correct 2646 ms 19836 KB Output is correct
14 Correct 4073 ms 19892 KB Output is correct
15 Correct 4279 ms 25148 KB Output is correct
16 Correct 4066 ms 34276 KB Output is correct
17 Correct 4090 ms 32232 KB Output is correct