Submission #369603

#	Time	Username	Problem	Language	Result	Execution time	Memory
369603		chubyxdxd	Race (IOI11_race)	C++11	100 / 100	812 ms	53356 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define sc second
#define ff first/*
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 500000

static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;*/
using namespace std;
typedef pair<int,int> ii;
/*inline 
void my_assert(int e) {if (!e) abort();}
 
void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&N,&K));
  for(i=0; i<N-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  my_assert(1==scanf("%d",&solution));
  }*/
set<ii> G[200010];
int exist[1000010];
int sz[200010];
int edgecnt[1000010];
int tt;
int n,k;
int dfs(int node,int pad){
  sz[node]=1;
  for(auto i:G[node]){
    if(i.ff==pad)continue;
    sz[node]+=dfs(i.ff,node);
  }
  return sz[node];
}
int centroid(int node,int pad,int tam){
  //cout<<node<<endl;
  for(auto i:G[node]){
    if(i.ff==pad)continue;
    if(sz[i.ff]>tam/2)return centroid(i.ff,node,tam);
  }
  return node;
}
int dfs2(int node,int pad,int dis,int edge,int comp,vector<ii>& v){
  //cout<<node<<endl;
  int want=k-dis;
  int ans=1e9;
  if(want>=0 && exist[want]==comp){
    ans=min(ans,edgecnt[want]+edge);
  }
  //cout<<k<<endl;
  if(dis<=k){
    v.push_back({dis,edge});
    for(auto i:G[node]){
      if(i.ff==pad)continue;
      ans=min(ans,dfs2(i.ff,node,dis+i.sc,edge+1,comp,v));
    }
  }
  return ans;
}
int solve(int node,int pad){
  int subsz=dfs(node,pad);
  int piv=centroid(node,pad,subsz);
  //cout<<123<<endl;
  int ans=1e9;
  int ac=++tt;
  exist[0]=ac;edgecnt[0]=0;
  for(auto i:G[piv]){
    vector<ii> tmp;
    ans=min(ans,dfs2(i.ff,piv,i.sc,1,ac,tmp));
    //cout<<ans<<" "<<ac<<endl;
    for(auto j:tmp){
      if(exist[j.ff]!=ac || (exist[j.ff]==ac && edgecnt[j.ff]>j.sc)){
	exist[j.ff]=ac;
	edgecnt[j.ff]=j.sc;
      }
    }
  }
  vector<ii> tmp (G[piv].begin(),G[piv].end());
  for(auto i:tmp){
    G[i.ff].erase(ii(piv,i.sc));
    G[piv].erase(i);
    ans=min(ans,solve(i.ff,piv));
    //cout<<ans<<" "<<ac<<endl;
  }
  // cout<<ans<<" "<<ac<<endl;
  return ans;
}
int best_path(int N, int K, int H[][2], int L[])
{
  tt=0;
  k=K;
  memset(exist,0,sizeof exist);
  for(int i=0;i<N-1;i++){
    int a=H[i][0];
    int b=H[i][1];
    G[a].insert(ii(b,L[i]));
    G[b].insert(ii(a,L[i]));
  }
  //cout<<123<<endl;
  int h=solve(1,0);
  if(h==1e9)return -1;
  return h;
}/*
int main()
{
  int ans;
  read_input();
  ans = best_path(N,K,H,L);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);
 
  return 0;
}
 */

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