Submission #221491

#	Time	Username	Problem	Language	Result	Execution time	Memory
221491		a_player	Race (IOI11_race)	C++14	43 / 100	3085 ms	40432 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define f first
#define s second
  
using namespace std;
  
const int nax=2e5+5;
const int vax=1e6+5;
typedef long long ll;
  
vector<pair<int,int>  > grafo[nax];
int ans=INT_MAX;
int N,K;
int ss,cc;
pair<int,int> m[vax];
vector<pair<int,int> > vv;
bitset<nax> vis;
int in;
void incl(int n, int a, int d, int v){
    if(K<v)return;
    if(a!=-1){
      if(v==K)ans=min(ans,d);
    if(m[K-v].s==in)ans=min(ans,m[K-v].f+d);
    vv.push_back({v,d});
    }
    for(auto x:grafo[n]){
      if(!vis[x.f]&&x.f!=a){
      incl(x.f,n,d+1,v+x.s);
      }
      if(a==-1){
        while(!vv.empty()){
            auto p=vv.back();
            vv.pop_back();
            if(m[p.f].s==in)m[p.f].f=min(m[p.f].f,p.s);
            else m[p.f]={p.s,in};
        }
      }
    }
}
int findc(int n, int a, int num){
  int s=0;
  int mas=0;
      for(auto x:grafo[n]){
        if(x.f!=a&&!vis[x.f]){
          int p=findc(x.f,n,num);
          s+=p;
          mas=max(mas,p);
        }
      }
      if(mas<=num/2)cc=n;
      return s+1;
}
int findsize(int n, int a){
  int s=0;
  for(auto x:grafo[n]){
    if(!vis[x.f]&&x.f!=a){
      s+=findsize(x.f,n);
    }
  }
  return s+1;
}
void centroid(int n){
  in=n;
  incl(n,-1,0,0);
  vis[n]=1;
  for(auto x:grafo[n]){
    if(vis[x.f])continue;
    ss=findsize(x.f,-1);
    findc(x.f,-1,ss);
    centroid(cc);
  }
  
}
  
int best_path(int N, int K, int H[][2], int L[]){
  ::N=N,::K=K;
  for(int i=0;i<N-1;i++){
    grafo[H[i][0]].push_back({H[i][1],L[i]});
    grafo[H[i][1]].push_back({H[i][0],L[i]});
  }
  for(int i=0;i<vax;i++)m[i]={-1,-1};
  findc(0,-1,N);
  centroid(cc);
  if(ans==INT_MAX)return -1;
  return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57