Submission #953394

#	Time	Username	Problem	Language	Result	Execution time	Memory
953394		sopaconk	Race (IOI11_race)	C++17	0 / 100	3 ms	6236 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define deb(x) cout<<#x<<": "<<x<<endl;
vector<int> dis;
vector<int> sz;
vector<int> par;
vector<vector<pair<int,int>>> adj;
vector<bool> vis;

int ans=1000000000;
int need;
void szdfs(int node, int parent){
  par[node]=parent;
  
  sz[node]=1;
  for(int i=0; i<(int) adj[node].size(); ++i){
    int x= adj[node][i].first;
    if(vis[x] || x==parent) continue;
    szdfs(x, node);
    sz[node]+=sz[x];
  }
}




int Centroid (int node, int siz){
  for(int i=0; i<(int) adj[node].size(); ++i){
    int x= adj[node][i].first;
    if(par[x]!=node || vis[x]) continue;
    if(sz[x] > siz/2){
      return Centroid ( x, siz);
    }  
  }
  return node;
}

queue<pair<int,int>>q;
void distances (int node,int parent, int d, int c){

  q.push({d, c});
   if(d<=need){
 
      if(dis[need-d]!=0){
        ans=min(ans, dis[need-d]+c);
      }
  }

  for(int i=0; i<(int) adj[node].size(); ++i){
    int x=adj[node][i].first;
    int y=adj[node][i].second;

    if(parent==x || vis[x]) continue;
    d+=y;

   
    
    distances(x, node, d, c+1);
  }
}


void Centroid_desc (int node){

    szdfs(node, -1);

    int root= Centroid ( node, sz[node]);

    for(int i=0; i<(int) adj[root].size(); ++i){
      if(vis[adj[root][i].first] ) continue; 
      distances(adj[root][i].first, root, adj[root][i].second, 1);

      while(!q.empty()){
        if(dis[q.front().first]!=0){
        dis[q.front().first]=min(dis[q.front().first], q.front().second);
        }
        else{
          dis[q.front().first]=q.front().second;
        }
        q.pop();
      }
    }
 
    if(dis[need]!=0){
      ans=min(ans, dis[need]);
    }
    vis[root]=1;
    for(int i=0; i<(int) adj[root].size(); ++i){
    
      if(vis[adj[root][i].first]) continue;

      Centroid_desc(adj[root][i].first);
    }
}






int best_path(int N, int K, int H[][2], int L[])
{

  dis.resize(1e6+5, 0);
  sz.resize(N);
  par.resize(N);
  adj.resize(N);
  vis.resize(N);
  for(int i=0; i<N-1; ++i){
    adj[H[i][0]].pb({H[i][1], L[i]});
    adj[H[i][1]].pb({H[i][0],L[i]});
  }
  need=K;
  Centroid_desc(0);

  if(ans==1000000000){
    ans=-1;
  }
  
  return ans;
}

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