제출 #247667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
247667		davi_bart	경주 (Race) (IOI11_race)	C++14	0 / 100	11 ms	11468 KiB

race

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;
//#define int ll
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
set<pair<int,int> >v[200010];
int mi=1000000000;
int KK;
vector<int> dim(200010),up(200010);
int dfs(int pos,int prec){
  up[pos]=prec;
  dim[pos]++;
  for(auto x:v[pos])if(x.first!=prec)dim[pos]+=dfs(x.first,pos);
  return dim[pos];
}

map<int,int> best;
void w(int pos,int prec,int dist,int archi){
  if(best.count(dist)==0 || archi<best[dist])best[dist]=archi;
  for(auto k:v[pos]){
    if(k.first==prec)continue;
    w(k.first,pos,dist+k.second,archi+1);
  }
}
void calcola(int pos){
  map<int,int> q;
  for(auto k:v[pos]){
    best.clear();
    w(k.first,pos,k.second,1);
    for(auto x:best){
      if(q.count(KK-x.first)){
        mi=min(mi,q[KK-x.first]+x.second);
      }
    }
    for(auto x:best){
      if(q.count(x.first)==0 || x.second<q[x.first])q[x.first]=x.second;
    }
  }
  //cout<<"calcolato: "<<pos<<" "<<mi<<endl;
}
void centroid(int pos);
void trova(int pos,int nodi){
  if(nodi==1)return;
  for(auto k:v[pos]){
    if(k.first==up[pos])continue;
    if(dim[k.first]>nodi/2){
      trova(k.first,nodi);
      return;
    }
  }
  calcola(pos);
  vector<int> vicini;
  for(auto k:v[pos]){
    if(v[k.first].find({pos,k.second})!=v[k.first].end())v[k.first].erase({pos,k.second});
    vicini.push_back(k.first);
    if(k.first!=up[pos])up[k.first]=-1;
  }
  v[pos].clear();
  int g=up[pos];
  while(g!=-1){
    dim[g]-=dim[pos];
    g=up[g];
  }
  //cout<<"pulito: "<<pos<<endl;
  up[pos]=-1;
  for(int x:vicini){
      centroid(x);
  }
}
void centroid(int pos){
  //cout<<"centroid: "<<pos<<" ";
  while(up[pos]!=-1){
    pos=up[pos];
  }
  //cout<<pos<<endl;
  trova(pos,dim[pos]);
}
int best_path(int N, int K, int H[][2], int L[]){
  for(int i=0;i<N-1;i++){
    v[H[i][0]].insert({H[i][1],L[i]});
    v[H[i][1]].insert({H[i][0],L[i]});
  }
  KK=K;
  dfs(0,-1);
  centroid(0);
  if(mi==1e9)return -1;
  else return mi;
}

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