제출 #419453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
419453		pliam	경주 (Race) (IOI11_race)	C++14	100 / 100	560 ms	104648 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define INF (int)1000000005
typedef long long ll;

ll k;
int ans;

struct node{
  map<ll,int> res;//(length,edges)
  ll add_l;
  int add_e;
  node(){
    res[0]=0;
    add_l=add_e=0;
  }
  void merge(node n,ll w){
    for(auto p:n.res){
      ll l=p.first+n.add_l+w;
      int e=p.second+n.add_e+1;
      if(res.count(k-l-add_l)) ans=min(ans,res[k-l-add_l]+add_e+e);
    }
    for(auto p:n.res){
      ll l=p.first+n.add_l+w-add_l;
      int e=p.second+n.add_e+1-add_e;
      if(res.count(l)) res[l]=min(res[l],e);
      else res[l]=e;
    }
  }
  void init_big(ll w){
    add_e+=1;
    add_l+=w;
    res[-add_l]=-add_e;
    if(res.count(k-add_l)) ans=min(ans,res[k-add_l]+add_e);
  }
};

node arr[MAXN];
int rep[MAXN];

vector<pair<int,ll>> adj[MAXN];//(to,weight)

void dfs(int curr,int par=-1){
  int big_c=-1;
  ll w_big=0;
  for(auto p:adj[curr]){
    int to=p.first;
    ll w=p.second;
    if(to==par) continue;
    dfs(to,curr);
    if(big_c==-1||arr[rep[big_c]].res.size()<arr[rep[to]].res.size()){
      big_c=to;
      w_big=w;
    }
  }
  if(big_c==-1){
    rep[curr]=curr;
    return;
  }else{
    rep[curr]=rep[big_c];
    arr[rep[big_c]].init_big(w_big);
  }
  for(auto p:adj[curr]){
    int to=p.first;
    ll w=p.second;
    if(to==par||to==big_c) continue;
    arr[rep[big_c]].merge(arr[rep[to]],w);
    rep[to]=rep[big_c];
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  ans=INF;
  k=K;
  for(int i=0;i<N-1;i++){
    adj[H[i][0]].push_back({H[i][1],L[i]});
    adj[H[i][1]].push_back({H[i][0],L[i]});
  }
  dfs(0);
  return ans==INF?-1:ans;
}

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