oj.uz

Submission #805205

# Submission time Handle Problem Language Result Execution time Memory
805205 2023-08-03T14:01:11 Z aymanrs Jousting tournament (IOI12_tournament) C++14
0 / 100
 218 ms 262144 KB 
#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-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 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 = f(que(S[i]+1, BIT), r), e = f(que(E[i]+1, BIT), r), 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);
    }
    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.0

# Verdict Execution time Memory Grader output
1 Runtime error 218 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 19764 KB Output isn't correct
2 Halted 0 ms 0 KB -