oj.uz

Submission #338569

# Submission time Handle Problem Language Result Execution time Memory
338569 2020-12-23T12:40:19 Z codebuster_10 Regions (IOI09_regions) C++17
25 / 100
 8000 ms 61528 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()
/**
 * 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 9 ms 384 KB Output is correct
6 Correct 20 ms 492 KB Output is correct
7 Correct 34 ms 620 KB Output is correct
8 Correct 34 ms 748 KB Output is correct
9 Correct 57 ms 1644 KB Output is correct
10 Correct 192 ms 2536 KB Output is correct
11 Correct 703 ms 3636 KB Output is correct
12 Correct 610 ms 5036 KB Output is correct
13 Correct 1612 ms 5696 KB Output is correct
14 Correct 6435 ms 7080 KB Output is correct
15 Correct 6499 ms 11916 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8025 ms 18532 KB Time limit exceeded
2 Execution timed out 8071 ms 19036 KB Time limit exceeded
3 Execution timed out 8080 ms 23388 KB Time limit exceeded
4 Correct 1004 ms 7404 KB Output is correct
5 Correct 1109 ms 10464 KB Output is correct
6 Execution timed out 8066 ms 12776 KB Time limit exceeded
7 Execution timed out 8015 ms 17124 KB Time limit exceeded
8 Execution timed out 8010 ms 28380 KB Time limit exceeded
9 Execution timed out 8083 ms 38108 KB Time limit exceeded
10 Execution timed out 8042 ms 48028 KB Time limit exceeded
11 Execution timed out 8092 ms 50260 KB Time limit exceeded
12 Execution timed out 8100 ms 46936 KB Time limit exceeded
13 Execution timed out 8028 ms 47964 KB Time limit exceeded
14 Execution timed out 8029 ms 50008 KB Time limit exceeded
15 Execution timed out 8100 ms 54104 KB Time limit exceeded
16 Execution timed out 8023 ms 61528 KB Time limit exceeded
17 Execution timed out 8029 ms 59868 KB Time limit exceeded