| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 203912 | kimjg1119 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <random>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
int n, k, ans = INF;
int siz[202020], chk[202020];
vector<pii> adj[202020];
int find_size(int x, int par) {
int ret = 1;
for (auto th : adj[x]) {
if (th.first == par || chk[th.first]) continue;
ret += find_size(th.first, x);
}
return siz[x] = ret;
}
int get_cent(int x, int par, int cnt) {
for (auto th : adj[x]) {
if (th.first == par || chk[th.first]) continue;
if (siz[th.first] > cnt / 2) return get_cent(th.first, x, cnt);
}
return x;
}
vector<pii> all_path;
void find_path(int x, int par, int len, int dep) {
if (len > k) return;
all_path.emplace_back(len, dep);
for (auto th : adj[x]) {
if (th.first == par || chk[th.first]) continue;
find_path(th.first, x, len + th.second, dep + 1);
}
}
void solve(int x) {
int cal = find_size(x, x);
int cent = get_cent(x, x, cal);
// cent를 지나는 경로들
all_path.clear();
find_path(cent, cent, 0, 0);
sort(all(all_path));
vector<pii> path;
for (auto hr : all_path) {
if (!path.empty() && path.back().first == hr.first) continue;
path.push_back(hr);
}
int ri = sz(path) - 1;
for (int i = 0; i < ri; i++) {
int left = k - path[i].first;
while (ri > i + 1 && path[ri].first > left) ri--;
if (path[ri].first == left)
ans = min(ans, path[i].second + path[ri].second);
}
// cent를 지나지 않는 경로들
chk[cent] = 1;
for (auto th : adj[cent]) {
int thv = th.first;
if (chk[thv]) continue;
solve(thv);
}
}
int best_path(int N, int K, vector<vector<int> > H, vector<int> L) {
n = N; k = K;
for (int i = 0; i < sz(H); i++) {
int a = H[i][0], b = H[i][1];
adj[a].emplace_back(b, L[i]);
adj[b].emplace_back(a, L[i]);
}
solve(0);
if (ans == INF) return -1;
else return ans;
}