| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 962791 | PoPularPlusPlus | Jousting tournament (IOI12_tournament) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
}
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;
}
int range_sum(int l , int r){
return sum(r) - sum(l-1);
}
};
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;
break;
}
else {
l = mid + 1;
}
}
vector<int> v;
for(int pos = ans, cnt = s[i]; cnt <= e[i]; cnt++,pos++){
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] , 0);
}
}
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);
//cout << tp << ' ';
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;
}
//cout << tp << ' ';
}
res = max(res , dis(i , lca));
}
cout << res << endl;
return res;
}