Submission #221498

#	Time	Username	Problem	Language	Result	Execution time	Memory
221498		a_player	Race (IOI11_race)	C++14	100 / 100	537 ms	37744 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&&s>=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: 57 / 57