oj.uz

Submission #805230

# Submission time Handle Problem Language Result Execution time Memory
805230 2023-08-03T14:17:55 Z aymanrs Jousting tournament (IOI12_tournament) C++14
100 / 100
 122 ms 45888 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 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 mc;
}

Compilation message

tournament.cpp: In function 'int fs(int, int*, int)':
tournament.cpp:63:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     m = l+r>>1;
      |         ~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 560 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 556 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 428 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 5 ms 2512 KB Output is correct
3 Correct 2 ms 2132 KB Output is correct
4 Correct 4 ms 2384 KB Output is correct
5 Correct 4 ms 2268 KB Output is correct
6 Correct 4 ms 2132 KB Output is correct
7 Correct 5 ms 2488 KB Output is correct
8 Correct 5 ms 2384 KB Output is correct
9 Correct 2 ms 2132 KB Output is correct
10 Correct 6 ms 2384 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 19776 KB Output is correct
2 Correct 122 ms 45888 KB Output is correct
3 Correct 44 ms 38612 KB Output is correct
4 Correct 110 ms 43316 KB Output is correct
5 Correct 111 ms 42804 KB Output is correct
6 Correct 105 ms 39124 KB Output is correct
7 Correct 119 ms 44236 KB Output is correct
8 Correct 112 ms 44280 KB Output is correct
9 Correct 39 ms 38608 KB Output is correct
10 Correct 44 ms 38684 KB Output is correct