제출 #701379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
701379		mychecksedad	Race (IOI11_race)	C++17	0 / 100	11 ms	23764 KiB

race

#include <bits/stdc++.h>
#include <race.h>
using namespace std;
#define ll long long
const int M = 1e6;
#define pb push_back

struct Edge{
  int to, e;
};

int n, k, ans, s[M];
vector<Edge> g[M];
vector<bool> vis;

int pre(int v, int p){
  s[v] = 1;
  for(Edge U: g[v]){
    int u = U.to;
    if(!vis[u] && u != p) pre(u, v), s[v] += s[u];
  }
  return s[v];
}

int centro(int v, int p, int sz){
  for(Edge U: g[v]){
    int u = U.to;
    if(u != p && !vis[u] && s[u] * 2 >= sz)
      return centro(u, v, sz);
  }
  return v;
}

void dfs(int v, int p, map<ll, int> &S, int d, int dd){
  S[d] = (S[d] == 0 ? dd : min(dd, S[d]));
  for(Edge U: g[v]){
    int u = U.to;
    if(!vis[u] && u != p) dfs(u, v, S, min(d + U.e, INT_MAX/2), dd + 1);
  }
}

void centroid(int v){
  int C = centro(v, 0, pre(v, 0));
  map<ll, int> s;
  dfs(C, 0, s, 0, 0);

  for(auto u: s){
    if(u.first <= k)
      if(s.find(k - u.first) != s.end()){
        ans = min(ans, u.second + s[k - u.first]);
      }
  }

  vis[C] = 1;

  for(Edge U: g[C]){
    int u = U.to;
    if(!vis[u]) 
      centroid(u);
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  n = N, k = K, ans = N + 1;
  for(int i = 0; i < n - 1; ++i){
    g[H[i][0] + 1].pb({H[i][1] + 1, L[i]});
    g[H[i][1] + 1].pb({H[i][0] + 1, L[i]});
  }
  vis.resize(n + 1);

  centroid(1);

  return (ans == N + 1 ? -1 : ans);
}

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