| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 464201 | ezdp | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC target ("sse4")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define endl '\n'
#define pb push_back
#define fr first
#define sc second
#define ll long long int
#define ld long double
#define bit(idx) idx&(-idx)
#define bin(x) bitset<32>(x).to_string()
#define all(A) A.begin(), A.end()
#define de(x) cout << #x << " = " << x << endl;
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using matrix = vector<vector<T>>;
/// find_by_order(x) -> x-th element in the set
/// order_of_key(x) -> how many elements are smaller than x
/// insert(x) -> inserts x into the set
const ll MAXN = 2e5 + 5;
const ll MAXK = 1e6 + 6;
const ll INF = 1e16 + 16;
ll n, k, ans = INF, used[MAXN], sz[MAXN], mn[MAXK];
matrix<pair<ll, ll>> G;
void dfs_ans(ll u, ll p, ll len, ll depth){
if(len > k) return;
ans = min(ans, mn[k - len] + depth);
for(auto [v, l] : G[u]){
if(!used[v] && v != p){
dfs_ans(v, u, len + l, depth + 1);
}
}
}
void dfs_add(ll u, ll p, ll len, ll depth){
if(len > k) return;
mn[len] = min(mn[len], depth);
for(auto [v, l] : G[u]){
if(!used[v] && v != p){
dfs_add(v, u, len + l, depth + 1);
}
}
}
void dfs_clear(ll u, ll p, ll len, ll depth){
if(len > k) return;
mn[len] = INF;
for(auto [v, l] : G[u]){
if(!used[v] && v != p){
dfs_clear(v, u, len + l, depth + 1);
}
}
}
ll find_size(ll u, ll p = -1){
if(!used[u]) return 0;
sz[u] = 1;
for(auto [v, l] : G[u]){
if(v != p && !used[v]){
sz[u] += find_size(v, u);
}
}
return sz[u];
}
ll find_centroid(ll u, ll p, ll cn){
for(auto [v, l] : G[u]){
if(sz[v] > cn / 2 && v != p && !used[v]){
return find_centroid(v, u, cn);
}
}
return u;
}
void init_centroid(ll u = 1, ll p = -1){
find_size(u);
ll c = find_centroid(u, -1, sz[u]);
mn[0] = 0;
for(auto [v, l] : G[c]){
if(!used[v]){
dfs_ans(v, c, l, 1);
dfs_add(v, c, l, 1);
}
}
dfs_clear(c, c, 0, 0);
used[c] = true;
for(auto v : G[c]){
if(!used[v]){
init_centroid(v, c);
}
}
}
int best_path(int N, int K, int h[][2], int L[]){
n = N; k = K;
G = matrix<pair<ll, ll>>(n + 1);
for(int i = 0; i < n - 1; i ++){ G[h[i][0]].pb({h[i][1], L[i]}); G[h[i][1]].pb({h[i][0], L[i]}); }
for(int i = 0; i < MAXK; i ++) mn[i] = INF;
init_centroid();
return (ans == INF ? -1 : ans);
}
/**
int main(){
int N, K; cin >> N >> K;
int h[N][2], L[N];
for(int i = 0; i < N - 1; i ++) cin >> h[i][0] >> h[i][1] >> L[i];
cout << best_path(N, K, h, L) << endl;
}
*/