Submission #953386

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

race

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

int ans=1e6;
int need;
void szdfs(int node, int parent){
  par[node]=parent;
  deb(par[node]);
  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){
  deb(node);
  q.push({d, c});
   if(d<=need){
      deb(dis[need-d]);
      if(dis[need-d]!=0){
        ans=min(ans, dis[need-d]+c);
      }
  }
  deb(d);
  deb(c);
  for(int i=0; i<(int) adj[node].size(); ++i){
    int x=adj[node][i].first;
    int y=adj[node][i].second;
    deb(x);
    deb(y);
    if(parent==x || vis[x]) continue;
    d+=y;
    deb(d);
    deb(need);
    
   
    
    distances(x, node, d, c+1);
  }
}


void Centroid_desc (int node){
  deb("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaAA");
  deb(node);
    szdfs(node, -1);
    deb(sz[0]);
    int root= Centroid ( node, sz[node]);
    deb(root);
    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);
      deb(adj[root][i].first);
      while(!q.empty()){
        deb(q.front().first);
        deb(q.front().second);
        dis[q.front().first]=min(dis[q.front().first], q.front().second);
        q.pop();
      }
    }
    deb(ans);
    if(dis[need]!=0){
      ans=min(ans, dis[need]);
    }
    vis[root]=1;
    for(int i=0; i<(int) adj[root].size(); ++i){
      deb(adj[root][i].first);
      if(vis[adj[root][i].first]) continue;
      deb(i);
      Centroid_desc(adj[root][i].first);
    }
}






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

  dis.resize(K+5, 1e6);
  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);
  deb("HI");
  deb(ans);
  if(ans==1e6){
    ans=-1;
  }
  deb(ans);
  return ans;
}

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