Submission #805229

#	Time	Username	Problem	Language	Result	Execution time	Memory
805229		aymanrs	Jousting tournament (IOI12_tournament)	C++14	0 / 100	57 ms	19780 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 add(int i, int BIT[], int n){
  while(i <= n){
    BIT[i]++;
    i += i&-i;
  }
}
void sub(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;
  bool s = u->d < v->d;
  if(s) 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(s) d = 0;
  if(u == v) return d-1;
  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 fs(int s, int BIT[], int N){
  s++;
  int l = 1, r = N, m, b = N;
  while(l <= r){
    m = l+r>>1;
    if(que(m, BIT) >= s){
      b = m;
      r = m-1;
    } else l = m+1;
  }
  return b-1;
}
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;
    add(i+1, 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 = fs(S[i], BIT, N), e = fs(E[i], BIT, N), cur = f(s+1, r);
    while(cur <= e){
      nw->l.push_back(&g[a[cur]]);
      sub(cur+1, BIT, N);
      cur = r[cur] = f(cur+1, r);
    }
    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 = INT_MIN, 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 mx;
}

Compilation message (stderr)

tournament.cpp: In function 'int fs(int, int*, int)':
tournament.cpp:63:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     m = l+r>>1;
      |         ~^~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:107:21: warning: variable 'mc' set but not used [-Wunused-but-set-variable]
  107 |   int mx = INT_MIN, mc = -1;
      |                     ^~

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