Submission #962834

#	Time	Username	Problem	Language	Result	Execution time	Memory
962834		PoPularPlusPlus	Jousting tournament (IOI12_tournament)	C++17	0 / 100	20 ms	10588 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

#define pb(x) push_back(x)

const int N = 100003 , L = 22;

struct dsu {
	vector<int> p;
	vector<int> top;

	void init(int n){
		p.resize(n + 1);
		top.resize(2*(n + 1));

		for(int i = 0; i <= n; i++){
			p[i] = i;
			top[i] = i;
		}
		for(int i = n; i <= 2*n; i++){
			top[i] = i;
		}
	}
 
	int get(int x){
		return p[x] = (p[x] == x ? x : get(p[x]));
	}

	int get_parent(int x){
		return top[x] = (top[x] == x ? x : get(top[x]));
	}
 
	void unio(int x , int y){
		x = get(x);
		y = get(y);
		if(y > x)swap(x,y);
		p[y] = x;
	}

	void put_parent(int x , int y){
		top[x] = y;
	}
};

struct Fen {
	int siz;
	vector<int> tree;
 
	void init(int n){
		siz = n;
		tree.assign(n + 5,0);
	}
 
	void set(int i, int val){
		i++;
		while(i <= siz){
			tree[i]+=val;
			i += (i & -i);
		}
	}
 
	int sum(int i){
		i++;
		int ans = 0;
		while(i > 0){
			ans += tree[i];
			i -= (i & -i);
		}
		return ans;
	}
};

vector<int> adj[2*N];
int up[2*N][L] , tin[2*N] , tout[2*N] , timer;

void dfs(int node , int par){
	//cout << node << ' ' << par << endl;
	tin[node] = timer++;
	up[node][0] = par;
	for(int i = 1; i < L; i++){
		up[node][i] = up[up[node][i-1]][i-1];
	}
	for(int i : adj[node]){
		dfs(i , node);
	}
	tout[node] = timer++;
}

bool is_ancestor(int x, int y){
	return tin[x] <= tin[y] && tout[x] >= tout[y];
}

int find(int x , int y){
	if(is_ancestor(x,y))return x;
	if(is_ancestor(y,x))return y;
	for(int i = L - 1; i >= 0; i--){
		if(!is_ancestor(up[x][i] , y)){
			x = up[x][i];
		}
	}
	return up[x][0];
}

int dis(int x , int y){
	int ans = 0;
	for(int i = L - 1; i >= 0; i--){
		if(!is_ancestor(up[x][i] , y)){
			x = up[x][i];
			ans += (1 << i);
		}
	}
	return ans;
}

int GetBestPosition(int n, int m, int r, int *arr, int *s,int *e){
	Fen ft;
	ft.init(n + 1);
	for(int i = 0; i < n; i++){
		ft.set(i , 1);
	}
	int cur = n;
	dsu d;
	d.init(n + 1);
	for(int i = 0; i < m; i++){
		int l = 0 , r = n-1;
		int ans = 0;
		while(l <= r){
			int mid = (l + r)/2;
			int x = ft.sum(mid);
			if(x > s[i]){
				r = mid - 1;
			}
			else if(x == s[i]){
				ans = mid + 1;
				r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
		vector<int> v;
		for(int pos = ans, cnt = s[i]; cnt <= e[i]; cnt++,pos++){
			while(pos >= n){
				;
			}
			int last = d.get(pos);
			v.pb(last);
			pos = last;
			//cout << cnt << ' ' << s[i] << ' ' << e[i] << '\n';
		}
		//cout << '\n';
		/*for(int it : v){
			//cout << it << ' ';
			adj[cur].pb(d.get_parent(it));
			d.put_parent(d.get_parent(it) , cur);
		}*/
		//cout << '\n';
		cur++;
		/*for(int j = 0; j < v.size() - 1; j++){
			d.unio(v[j] , v[j+1]);
			ft.set(v[j] , -1);
		}*/
	}

	vector<int> better;
	for(int i = 0; i < n - 1; i++){
		if(arr[i] > r){
			better.pb(i);
		}
	}

	timer = 0;
	dfs(cur - 1 , cur-1);

	int j = 0;
	int res = 0;
	for(int i = 0; i < n; i++){
		while(j < better.size() && better[j] < i){
			j++;
		}
		int lca = cur - 1;
		if(j > 0){
			int tp = find(better[j-1] , i);
			if(is_ancestor(lca , tp)){
				lca = tp;
			}
		}
		if(j < better.size()){
			int tp = find(better[j] + 1, i);
			if(is_ancestor(lca,tp)){
				lca = tp;
			}
		}
		res = max(res , dis(i , lca));
	}
	//cout << res << endl;
	return res;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:178:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |   while(j < better.size() && better[j] < i){
      |         ~~^~~~~~~~~~~~~~~
tournament.cpp:188:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |   if(j < better.size()){
      |      ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51