제출 #1309632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309632		husseinjuanda	경주 (Race) (IOI11_race)	C++20	100 / 100	1163 ms	81304 KiB

race

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

vector<vector<pair<int, int>>> g;

vector<int> sz;
vector<bool> vis;

int fi = 0;

void dfs(int k, int p){
  sz[k] = 1;
  for(int i = 0; i < g[k].size(); i++){
    if(g[k][i].first == p || vis[g[k][i].first]) continue;
    dfs(g[k][i].first, k);
    sz[k] += sz[g[k][i].first];
  }
}

int mn = 1e9;

int find_cen(int k, int s, int p){
  for(int i = 0; i < g[k].size(); i++){
    if(vis[g[k][i].first] || g[k][i].first == p) continue;
    if(sz[g[k][i].first] > s/2){
      return find_cen(g[k][i].first, s, k);
    }
  }
  return k;
}

int co = 0;

void fsz(int k, int p){
  co++;
  for(int i = 0; i < g[k].size(); i++){
    if(vis[g[k][i].first] || g[k][i].first == p) continue;
    fsz(g[k][i].first, k);
  }
}

vector<pair<long long, int>> pen;

void dfs1(int k, int p, int cur, int co){
  pen.push_back({cur, co+1});
  for(int y = 0; y < g[k].size(); y++){
    if(vis[g[k][y].first] || g[k][y].first == p) continue;
    dfs1(g[k][y].first, k, cur+g[k][y].second, co+1);
  }
}

void solve(int k){
  if(vis[k]) return;
  //find cen
  co = 0;
  fsz(k, 0);
  dfs(k, 0);
  int cen = find_cen(k, co, 0);
  // cout << cen << "\n";
  vis[cen] = true;
  map<long long, int> mp;
  for(int i = 0; i < g[cen].size(); i++){
    if(vis[g[cen][i].first]) continue;
    pen.clear();
    dfs1(g[cen][i].first, 0, g[cen][i].second, 0);
    for(auto y : pen){
      // cout << y.first << " J\n";
      long long cur = fi-y.first;
      if(cur == 0){
        mn = min(mn, y.second);
      }
      if(mp[cur] == 0) continue;
      mn = min(mn, mp[cur]+y.second);
    }
    for(auto y : pen){
      if(mp[y.first] == 0){
        mp[y.first] = y.second;
        // cout << mp[1] << " K\n";
      }else{
        mp[y.first] = min(mp[y.first], y.second);
      }
    }
  }
  for(int i = 0; i < g[cen].size(); i++){
    if(vis[g[cen][i].first]) continue;
    solve(g[cen][i].first);
  }
  solve(k);
}

int best_path(int N, int K, int H[][2], int L[])
{
  fi = K;
  vis.resize(N+1);
  g.resize(N+1);
  sz.resize(N+1);
  for(int i = 0; i < N-1; i++){
    g[H[i][0]+1].push_back({H[i][1]+1, L[i]});
    g[H[i][1]+1].push_back({H[i][0]+1, L[i]});
  }
  dfs(1, 0);
  solve(1);
  if(mn == 1e9){
    mn = -1;
  }
  return mn;
}

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