제출 #701383

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

race

#include <bits/stdc++.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;
}

vector<pair<int, int>> ddd;
void dfs(int v, int p, map<int, int> &S, int d, int dd){
  ddd.pb({d, dd});
  if(d == k){
  	ans = min(ans, dd);
  }
  if(d <= k && S.find(k - d) != S.end())
  	ans = min(ans, dd + S[k - d]);
  for(Edge U: g[v]){
    int u = U.to;
    if(!vis[u] && u != p) 
    	dfs(u, v, S, min(d + U.e, 1000000000), dd + 1);
  }
}

void centroid(int v){
  int C = centro(v, 0, pre(v, 0));
  map<int, int> s; 
  for(Edge U: g[C]){
  	int u = U.to;
  	if(!vis[u]){
  		ddd.clear();
  		dfs(u, C, s, U.e, 1);
  		for(auto v: ddd) s[v.first] = s[v.first] == 0 ? v.second : min(s[v.first], v.second);
  	}
  }

  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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57