제출 #1369593

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

race

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

const int MXK = 1e6+6, INF = 1e9+7, MXN=2e5+5;
int mnpath[MXK], removed[MXN], sz[MXN];

int n,k;

vector<pair<int,int>> adj[MXN];


int sub(int u, int prv) {
  sz[u] = 1;
  for (auto [v,w] : adj[u]) {
    if (removed[v] || v == prv) continue;
    sz[u]+=sub(v,u);
  }
  return sz[u];
}

int fndcentroid(int u, int prv, int total) {
  for (auto [v, w] : adj[u]) {
    if (removed[v] || v==prv) continue;

    if (sz[v] > total/2) return fndcentroid(v, u, total);
  }
  return u;
}

int ans = INF;
stack<pair<int,int>> st;
void dfs(int u, int prv, int sm, int cnt) {
  if (sm>k) return;

  if (k-sm >= 0) ans = min(ans, mnpath[k-sm] + cnt);

  for (auto [v,w] : adj[u]) {
    if (v==prv || removed[v]) continue;
    dfs(v, u, sm+w, cnt+1);
  }
  st.push({sm, cnt});
}
void decomp(int node) {
  int total = sub(node, node);

  int centroid = fndcentroid(node, node, total);

  mnpath[0] = 0;
  removed[centroid] = true;

  vector<int> clearmn={0};
  for (auto [v,w] : adj[centroid]) {
    if (removed[v]) continue;

    dfs(v, centroid, w, 1);

    while (!st.empty()) {
      auto [sm, cnt] = st.top(); st.pop();
      clearmn.push_back(sm);
      mnpath[sm] = min(mnpath[sm], cnt);
    }
  }

  for (auto &x : clearmn) mnpath[x] = INF;
  clearmn.clear();
  
  for(auto [v,w] : adj[centroid]) {
    if (removed[v]) continue;
    decomp(v);
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  n=N;
  k=K;

  fill(mnpath, mnpath+MXK, INF); 

  for (int i=0; i<n-1; i++) {
    int u=H[i][0], v=H[i][1], w = L[i];
    adj[u].push_back({v,w});
    adj[v].push_back({u,w});
  }

  decomp(0);
  return (ans == INF ? -1 : ans);
}

• 서브태스크 1: 9 / 9
• 서브태스크 2: 12 / 12
• 서브태스크 3: 22 / 22
• 서브태스크 4: 57 / 57