Submission #592086

#	Time	Username	Problem	Language	Result	Execution time	Memory
592086		Hackapie	Race (IOI11_race)	C++17	9 / 100	3056 ms	18928 KiB

race

#include <bits/stdc++.h>
#define ll long long int
#define mp make_pair
#include "race.h"
using namespace std;
int ans;
const ll lim=200005;
vector<bool> vis(lim);
vector<pair<int,int>> g[lim]; 
vector<int> par(lim); 
int kk;
vector<int> sz(lim),ok(lim+100);
int timer=1;
map<int,int>add;
void dfs_sz(int node,int p){
  sz[node]=1;
  for(auto x:g[node]){
    if(x.first==p)continue;
    if(vis[x.first])continue;
    dfs_sz(x.first,node);
    sz[node]+=sz[x.first];
  }
}
int centroid(int &cnt,int node,int p){
  for(auto x:g[node]){
    if(x.first==p)continue;
    if(vis[x.first])continue;
    if(sz[x.first]>(cnt/2)){
      centroid(cnt,x.first,node);
    }
  }
  return node;
}
 
void solve(int node,int p,ll dis,int cnt,vector<pair<ll,ll>> &info){
  if(dis<=kk && ok[kk-dis]==timer){                        //if a valid path exists
    ans=min(ans,cnt+add[kk-dis]);
  }
  if(dis<=kk){                         
    info.push_back({dis,cnt});                      //record information
    for(auto x:g[node]){
      if(x.first==p)continue;
      if(!vis[x.first]){
        solve(x.first,node,dis+x.second,cnt+1,info);
      }
    }
  }
}
void create(int root,int p){
  dfs_sz(root,p);                      //-> find size
  int c=centroid(sz[root],root,p);     //find new centroid
  vis[c]=true;                          //visited
  ++timer;
  ok[0]=timer;
  add[0]=0;
  par[c]=root;                        //updating info
  for(auto x:g[c]){                   //for every subtree in centroid find paths ..will help in finding if there exists some path that posses through centrod
    if(vis[x.first])continue;
    if(x.first==p)continue;
    vector<pair<ll,ll>> v;
    solve(x.first,c,x.second,1,v);
    for(auto y:v){                       //updating info
      if(ok[y.first]!=timer){ 
        ok[y.first]=timer;
        add[y.first]=y.second;
      }else{
        if(add[y.first]>y.second){
          ok[y.first]=timer;
          add[y.first]=y.second;
        }
      }
    }
  }
  for(auto x:g[c]){    
    if(x.first==p)continue;      //centroid decom
    if(!vis[x.first])create(x.first,c);
  }
 
}
int best_path(int n, int k, int h[][2], int l[])
{
  ans=2*n;
  vis.clear();
  sz.clear();
  par.clear();
  for(int i=1;i<=n;i++)g[i].clear();
  timer=1;
  kk=k;
  ok.clear();
  add.clear();
  for(int i=0;i<n-1;i++){
    g[h[i][0]].push_back({h[i][1],l[i]});
    g[h[i][1]].push_back({h[i][0],l[i]});
  }
  create(1,-1);
  if(ans==(2*n))ans=-1;
  return ans;
}

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