Submission #805174

#	Time	Username	Problem	Language	Result	Execution time	Memory
805174		aymanrs	Jousting tournament (IOI12_tournament)	C++14	0 / 100	49 ms	19828 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
int f(int i, int r[]){
  if(r[i] == i) return i;
  return r[i] = f(r[i], r);
}
void upd(int i, int BIT[], int n){
  while(i <= n){
    BIT[i]++;
    i += i&-i;
  }
}
int que(int i, int BIT[]){
  int ans = 0;
  while(i){
    ans += BIT[i];
    i -= i&-i;
  }
  return ans;
}
const int L = 18;
struct node {
  vector<node*> l;
  node* anc[L];
  node* root = NULL;
  int d;
};
node* roo;
void dfs(node* n, node* p, int d){
  n->root = roo;
  n->d = d;
  n->anc[0] = p;
  for(int i = 1;i < L;i++) n->anc[i] = n->anc[i-1]->anc[i-1];
  for(node* c : n->l) dfs(c, n, d+1);
}
int lca(node* u, node* v){
  if(u->root != v->root) return u->d;
  if(u->d < v->d) swap(u, v);
  int d = u->d - v->d;
  for(int i = 0;i < L;i++) if(d&(1<<i)) u = u->anc[i];
  if(u == v) return d;
  for(int i = L-1;i >= 0;i--) {
    if(u->anc[i] != v->anc[i]){
      d += 1<<i;
      u = u->anc[i];
      v = v->anc[i];
    }
  }
  return d;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  int r[N+1], BIT[N+1] = {0}, a[N], pr[N], nx[N];
  vector<node> g(N);
  r[N] = N;
  int c = -1;
  for(int i = 0;i < N;i++){
    r[i] = a[i] = i;
    upd(i+2, BIT, N);
  }
  for(int i = 0;i < N-1;i++){
    if(K[i] > R) c = i;
    pr[i] = c;
  }
  c = -1;
  for(int i = N-2;i >= 0;i--){
    if(K[i] > R) c = i;
    nx[i] = c;
  }
  for(int i = 0;i < C;i++){
    g.emplace_back();
    node* nw = &g[g.size()-1];
    int s = que(S[i]+1, BIT), e = que(E[i]+1, BIT), cur = f(s+1, r), ind = S[i]+2;
    while(cur <= e){
      nw->l.push_back(&g[a[cur]]);
      upd(ind, BIT, N);
      cur = r[cur] = f(cur+1, r);
      ind++;
    }
    nw->l.emplace_back(&g[a[s]]);
    a[s] = g.size()-1;
  }
  for(int i = g.size()-1;i >= 0;i--){
    if(!g[i].root) {
      roo = &g[i];
      dfs(&g[i], &g[i], 0);
    }
  }
  int mx = -1, mc = -1;
  for(int i = 0;i < N;i++){
    int t = g[i].d;
    if(i < N-1 && nx[i] != -1) t = min(t, lca(&g[i], &g[nx[i]+1]));
    if(i && pr[i-1] != -1) t = min(t, lca(&g[i], &g[pr[i-1]]));
    if(t > mx){
      mx = t;
      mc = i;
    }
  }
  return mc;
}

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