제출 #964556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964556		PoPularPlusPlus	마상시합 토너먼트 (IOI12_tournament)	C++17	100 / 100	119 ms	35884 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_parent(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);
		}
	}
	if(x != y)ans++;
	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;
	int ans_pos = 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;
			}
		}
		int sub = 0;
		if(r < n - 1)sub = 1;
		if(res < dis(i,lca) - sub){
			res = dis(i , lca) - sub;
			ans_pos = i;
		}
		res = max(res , dis(i , lca) - sub);
	}
	//cout << res << endl;
	return ans_pos;
}

컴파일 시 표준 에러 (stderr) 메시지

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:160:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |   for(int j = 0; j < v.size() - 1; j++){
      |                  ~~^~~~~~~~~~~~~~
tournament.cpp:180:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |   while(j < better.size() && better[j] < i){
      |         ~~^~~~~~~~~~~~~~~
tournament.cpp:190:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |   if(j < better.size()){
      |      ~~^~~~~~~~~~~~~~~

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