oj.uz

Submission #130704

# Submission time Handle Problem Language Result Execution time Memory
130704 2019-07-15T23:46:57 Z dragonslayerit Jousting tournament (IOI12_tournament) C++14
0 / 100
 274 ms 8564 KB 
#include <vector>

std::vector<int> children[200005];
int N;
int st[200005];

int query(int a,int b){
  int res=0;
  for(a+=N-1,b+=N-1;a<b;a>>=1,b>>=1){
    if(a&1) res=std::max(res,st[a++]);
    if(b&1) res=std::max(res,st[--b]);
  }
  return res;
}

int size[200005];
int depth[200005];
int deep[200005];
int R;

void dfs1(int node){
  size[node]=1;
  if(node<N){
    deep[node]=node;
  }
  for(int child:children[node]){
    dfs1(child);
    if(depth[child]+1>depth[node]){
      depth[node]=depth[child]+1;
      deep[node]=deep[child];
    }
    size[node]+=size[child];
  }
}

std::pair<int,int> best;

void dfs2(int node,int prefix,int suffix){
  if(query(prefix,N-suffix)<=R){
    best=std::max(best,{depth[node],-deep[node]});
  }
  
  suffix+=size[node];
  for(int child:children[node]){
    suffix-=size[child];
    dfs2(child,prefix,suffix);
    prefix+=size[child];
  }
}


int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
  ::N=N;
  ::R=R;
  std::vector<int> stand;
  for(int i=0;i<N;i++){
    stand.push_back(i);
  }
  for(int i=0;i<C;i++){
    for(int j=S[i];j<=E[i];j++){
      children[N+i].push_back(stand[S[i]]);
      stand.erase(stand.begin()+S[i]);
    }
    stand.insert(stand.begin()+S[i],N+i);
  }
  for(int i=0;i<N-1;i++){
    st[N-1+i]=K[i];
  }
  for(int i=N-2;i>0;i--){
    st[i]=std::max(st[i<<1],st[i<<1|1]);
  }
  dfs1(N+C-1);
  dfs2(N+C-1,0,0);
  return -best.second;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Incorrect 6 ms 5112 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 11 ms 5624 KB Output is correct
3 Incorrect 8 ms 5240 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

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