제출 #500584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500584		Joo	경주 (Race) (IOI11_race)	C++17	9 / 100	224 ms	50624 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int INF = 1e9, N = 2e5+10;

int dep[N], ans = INF;
long long qs[N];
vector<pair<int,int>> G[N];
map<long long, int> mp[N];

void dfs1(int u, int p){
  for(auto [v, w] : G[u]){
    if(v == p) continue;
    dep[v] = dep[u]+1;
    qs[v] = qs[u]+w;
    dfs1(v, u);
  }
}

void dfs2(int u, int p, const int &K){

  for(auto [v, w] : G[u]){
    if(v == p) continue;
    dfs2(v, u, K);

    if(mp[v].size() > mp[u].size()){
      swap(mp[v], mp[u]);
    }
  }

  for(auto [v, w] : G[u]){
    for(auto &[key, val] : mp[v]){
      long long tmp = K-key+2ll*qs[u];
      if(mp[u].find(tmp) != mp[u].end()){
        ans = min(ans, val+mp[u][tmp]-2*dep[u]);
      }
      if(mp[u].find(key) != mp[u].end()){
        mp[u][key] = min(mp[u][key], val);
      } else {
        mp[u][key] = val;
      }
    }
  }

  if(mp[u].find(K+qs[u]) != mp[u].end()){
    ans = min(ans, mp[u][K+qs[u]]-dep[u]);
  }
  mp[u][qs[u]] = dep[u];
}

int best_path(int N, int K, int H[][2], int L[])
{
  for(int i = 0; i < N-1; i++){
    int u = H[i][0], v = H[i][1];
    G[u].emplace_back(v, L[i]);
    G[v].emplace_back(u, L[i]);
  }

  if(DEBUG){
    for(int i = 0; i < N; i++){
      cout << "CUR : " << i << "\n";
      for(auto [v, w] : G[i]){
        cout << v << " " << w << "\n";
      }
      cout << "\n";
    }
  }

  dep[0] = 1;
  dfs1(0, -1);

  // for(int i = 0; i < N; i++) cout << dep[i] << " " << qs[i] << "\n";
  
  dfs2(0, -1, K);


  if(ans >= INF) ans = -1;
  
  return ans;
}
/*
int main(void){
  int N, K; cin >> N >> K;
  int H[N-1][2], L[N-1];
  for(int i = 0; i < N-1; i++) cin >> H[i][0] >> H[i][1] >> L[i];
  int res; cin >> res;

  int cal = best_path(N, K, H, L);

  cout << cal << " " << res << "\n";
}*/

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