Submission #875652

#	Time	Username	Problem	Language	Result	Execution time	Memory
875652		Huseyn123	Race (IOI11_race)	C++17	100 / 100	339 ms	94268 KiB

race

#include "race.h"
#include <bits/stdc++.h> 
#define MAX 200001
#define INF INT_MAX
using namespace std; 
multiset<pair<int,int>> a[MAX];
int k;
vector<int> dist; 
vector<int> dep; 
vector<vector<pair<int,int>>> g;
int res=INF;
void dfs(int v,int prev){
  a[v].insert(make_pair(dist[v],dep[v]));
  for(auto x:g[v]){
    if(x.first==prev){
      continue;
    }
    dist[x.first]=dist[v]+x.second;
    dep[x.first]=dep[v]+1;
    dfs(x.first,v);
    if(a[v].size()<a[x.first].size()){
      swap(a[v],a[x.first]);
    }
    for(auto y:a[x.first]){
      auto it=a[v].lower_bound(make_pair(k+2*dist[v]-y.first,0));
      if(it!=a[v].end() && (*it).first==k+2*dist[v]-y.first){
        res=min(res,(*it).second+y.second-2*dep[v]);
      }
    }
    for(auto y:a[x.first]){
      a[v].insert(y);
    }
  }
}
int best_path(int N, int K, int H[][2], int L[])
{
  k=K;
  g.resize(N+1); 
  dist.resize(N+1,0);
  dep.resize(N+1,0); 
  for(int i=0;i<N-1;i++){
    g[H[i][0]].push_back(make_pair(H[i][1],L[i]));
    g[H[i][1]].push_back(make_pair(H[i][0],L[i]));
  }
  dfs(0,-1);
  if(res==INF){
    res=-1;
  }
  return res;
}
/*
int main(){
    int n,k; 
    cin >> n >> k; 
    int h[n-1][2]; 
    int l[n];
    for(int i=0;i<n-1;i++){
        cin >> h[i][0] >> h[i][1]; 
    }
    for(int i=0;i<n-1;i++){
        cin >> l[i];
    }
    cout << "h" << " " << best_path(n,k,h,l) << "\n";
}
*/

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