| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 672177 | vjudge1 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define Baba_Sevawy ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ld long double
#define el '\n'
#define pi acos(-1)
#define F first
#define S second
#define sz(x) (int)(x).size()
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
return uniform_int_distribution<ll>(l, r)(gen);
}
const int NN = 2e5 + 5, M = 1e6 + 5, mod = 1e9 + 7, INF = 2e9;
int siz[NN], k;
ll f[M];
bool vis[NN];
vector<pair<ll, ll>>adj[NN];
vector<pair<ll, ll>>all;
vector<ll>sums;
int dfs_sz(int node, int par){
siz[node] = 1;
for(auto i : adj[node]){
if(i.F == par || vis[i.F]) continue;
siz[node] += dfs_sz(i.F, node);
}
return siz[node];
}
int dfs_centroid(int node, int par, int n){
for(auto i : adj[node])
if(i.F != par && !vis[i.F] && siz[i.F] > n / 2) return dfs_centroid(i.F, node, n);
return node;
}
void dfs_collect(int node, int par, int len, ll sum){
all.emplace_back(len, sum);
sums.emplace_back(sum);
for(auto i : adj[node]){
if(vis[i.F] || i.F == par) continue;
dfs_collect(i.F, node, len + 1, sum + i.S);
}
}
ll build(int node, int par){
int size = dfs_sz(node, par);
int centroid = dfs_centroid(node, par, size);
if(par == -1) par = centroid;
vis[centroid] = true;
ll ans = 1e9;
f[0] = 0;
for(auto i : adj[centroid]){
if(vis[i.F]) continue;
all.clear();
dfs_collect(i.F, centroid, 1, i.S);
for(auto j : all)
if(j.S <= k && f[k - j.S] != -1)
ans = min(ans, j.F + f[k - j.S]);
for(auto j : all) {
if (f[j.S] == -1) f[j.S] = j.F;
else f[j.S] = min(f[j.S], j.F);
}
}
for(auto &i : sums) if(i < M) f[i] = -1;
sums.clear();
for(auto i : adj[centroid]){
if(vis[i.F]) continue;
ans = min(ans, build(i.F, centroid));
}
return ans;
}