| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 886255 | AgentPengin | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
* author: AgentPengin ( Ð?c cô c?u b?i )
* created: 23.12.2022 10:08:02
* too lazy to update time
**/
#include<bits/stdc++.h>
#include "race.h"
#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
#define int ll
using namespace std;
const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 2e5 + 5;
int n,k,sz[MAXN],ans = inf;
vector<pair<int,int>> adj[MAXN];
bool deleted[MAXN];
int get_subtree_sizes(int u,int p = 0) {
sz[u] = 1;
for (auto v : adj[u]) {
if (!deleted[v.fi] && v.fi != p) {
sz[u] += get_subtree_sizes(v.fi,u);
}
}
return sz[u];
}
int find_centroid(int desired,int u,int p = 0) {
for (auto v : adj[u]) {
if (v.fi != p && !deleted[v.fi] && sz[v.fi] >= desired) {
return find_centroid(desired,v.fi,u);
}
}
return u;
}
unordered_map<int,int> mp;
vector<pair<int,int>> update;
void dfs(int u,int p,int len,int depth) {
if (len > k) return;
if (mp.count(k - len)) {
ans = min(ans,mp[k - len] + depth);
}
update.emplace_back(len,depth);
for (auto v : adj[u]) {
if (v.fi != p && !deleted[v.fi]) {
dfs(v.fi,u,len + v.se,depth + 1);
}
}
}
void solve(int u) {
int centroid = find_centroid(get_subtree_sizes(u) >> 1,u);
mp[0] = 0;
for (auto v : adj[centroid]) {
if (deleted[v.fi]) continue;
// solve for v
dfs(v.fi,centroid,v.se,1);
for (auto x : update) {
if (!mp.count(x.fi)) mp[x.fi] = x.se;
else mp[x.fi] = min(mp[x.fi],x.se);
}
// update for v
}
mp.clear();
deleted[centroid] = true;
for (auto v : adj[centroid]) {
if (!deleted[v.fi]) {
solve(v.fi);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N,k = K;
for (int i = 1;i < n;i++) {
int u,v,l;
u = H[i - 1][u];
v = H[i - 1][v];
l = L[i - 1];
}
solve(1);
if (ans > n) return -1;
else return ans;
}