Submission #338569

#	Time	Username	Problem	Language	Result	Execution time	Memory
338569		codebuster_10	Regions (IOI09_regions)	C++17	25 / 100	8100 ms	61528 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()
/**
 * Description: 1D range minimum query. Can also do queries 
 	* for any associative operation in $O(1)$ with D\&C
 * Source: KACTL
 * Verification: 
	* https://cses.fi/problemset/stats/1647/
	* http://wcipeg.com/problem/ioi1223
	* https://pastebin.com/ChpniVZL
 * Memory: O(N\log N)
 * Time: O(1)
 * Zero based indexing 
 * gives ans for [l, r]
 */
template<class T> struct RMQ { // floor(log_2(x))
	int level(int x) { 
    return 31 - __builtin_clz(x); 
  } 
	vector<T> v ; 
  vector<vector<int> > jmp;
	int comb(int a, int b) { // index of min
		return v[a]==v[b] ? min(a,b) : (v[a]<v[b] ? a : b) ; 
  } 
	void init(const vector<T> & _v) {
		v = _v; jmp = { vector<int> ((int)((v).size())) } ; 
    iota(begin(jmp[0]), end(jmp[0]), 0) ;
		for (int j = 1; 1<<j <= (int)((v).size()); ++j) {
			jmp.push_back(vector<int>((int)((v).size())-(1<<j)+1));
			for(int i=0; i < (int)((jmp[j]).size()) ; ++i){
        jmp[j][i] = comb(jmp[j-1][i], jmp[j-1][i+(1<<(j-1))]) ;
      } 
		}
	}
	int index(int l, int r) { // get index of min element
		assert(l <= r); 
    int d = level(r-l+1);
		return comb(jmp[d][l], jmp[d][r-(1<<d)+1]); 
  }
	T query(int l, int r) { 
    return v[index(l,r)]; 
  }
};
/**
 * Description: Euler Tour LCA. Compress takes a subset $S$ of nodes 
 	* and computes the minimal subtree that contains all the nodes 
	* pairwise LCAs and compressing edges. Returns a list of
	* \texttt{(par, orig\_index)} representing a tree rooted at 0. 
	* The root points to itself.
 * Time: O(N\log N) build, O(1) LCA, O(|S|\log |S|) compress
 * Source: USACO, Simon Lindholm (KACTL)
 * Verification: USACO Debug the Bugs
 	* https://codeforces.com/contest/1320/problem/E
 */
// include RMQ for this
struct LCA {
	int N; vector< vector<int> > adj;
	vector<int> depth, pos, par; // rev is for compress
	vector<pair<int, int> > tmp; 
  RMQ<pair<int, int> > r;
	void init(int _N) { 
    N = _N ; 
    adj.resize(N) ; 
		depth = pos = par = vector<int> (N) ; 
  }
	void ae(int x, int y) { // add edge
    adj[x].push_back(y), adj[y].push_back(x); 
  }
	void dfs(int x) {
		pos[x] = (int)(tmp.size()) ; 
    tmp.emplace_back(depth[x], x) ; 
		for(auto y:adj[x]) if (y != par[x]) {
			depth[y] = depth[ par[y] = x ] + 1;
      dfs(y) ;
			tmp.emplace_back(depth[x],x); 
    }
	}
	void gen(int R = 0) { 
    par[R] = R; 
    dfs(R); 
    r.init(tmp); 
  }
	int lca(int u, int v){
		u = pos[u], v = pos[v]; 
    if (u > v) swap(u,v);
		return r.query(u,v).second ; 
  }
	int dist(int u, int v) {
		return depth[u] + depth[v] - 2*depth[lca(u,v)]; 
  }
};
signed main(){
  fastio ;
  int N, R, Q; cin >> N >> R >> Q ;
  vector<int> home[R] ;
  LCA tree ;
  tree.init(N) ;
  f(i, 0, N){
    if(i == 0){
      int x ; cin >> x ; --x;
      home[x].push_back(i) ;
      continue ;
    }
    int x, y; cin >> x >> y ; --x,--y;
    tree.ae(i,x) ;
    home[y].push_back(i) ;
  }
  tree.gen() ;
  while(Q--){
    int r1, r2, ans = 0 ; cin >> r1 >> r2 ; --r1,--r2;
    cout << endl ;
    for(auto i:home[r1])
      for(auto j:home[r2]){
        if( tree.lca(i, j) == i) ans++ ;
      }
    cout << ans << endl ;
  }
}

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