| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 886410 | 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>
#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;
const int MAXC = 1e6 + 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;
int mx_len,cnt[MAXC];
void dfs(int u,int p,int len,int depth) {
if (len > k) return;
if (cnt[k - len] != -1) {
ans = min(ans,cnt[k - len] + depth);
}
mx_len = max(mx_len,len);
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);
cnt[0] = 0;
mx_len = 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 (cnt[x.fi] == -1) cnt[x.fi] = x.se;
else cnt[x.fi] = min(cnt[x.fi],x.se);
}
// update for v
update.clear();
}
fill(cnt,cnt + mx_len + 1,-1);
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 = 0;i < n - 1;i++) {
adj[H[i][0] + 1].emplace_back(H[i][1] + 1,L[i]);
adj[H[i][1] + 1].emplace_back(H[i][0] + 1,L[i]);
}
solve(1);
if (ans > n) return -1;
else return ans;
}
// agent pengin wants to take apio (with anya-san)