| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 900169 | subrat0018 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define nline "\n"
using uint = unsigned int;
using ull = unsigned long long;
const ll M = 1e9 + 7;
const ll M2 = 998244353;
const ll INF = 2e18;
const ll N = 1e6 + 10;
const double Degree = 57.2958;
/***************************************Debug***********************************************************/
/***************************************Debug***********************************************************/
/***************************************Debug***********************************************************/
#ifndef ONLINE_JUDGE
#define debug(x) cerr<< #x << " ";_print(x);cerr<<nline;
#else
#define debug(x)
#endif
void _print(int x) {cerr << x;}
void _print(bool x) {cerr << x;}
void _print(char x) {cerr << x;}
void _print(string x) {cerr << x;}
void _print(ll x) {cerr << x;}
void _print(ull x) {cerr << x;}
void _print(float x) {cerr << x;}
void _print(double x) {cerr << x;}
template<class T>void _print(set<T> v);
template<class T>void _print(vector<T> v);
template<class T>void _print(multiset<T> v);
template<class T>void _print(unordered_set<T> v);
template<class T, class V>void _print(map<T, V> v);
template<class T, class V>void _print(unordered_map<T, V> v);
template<class T>void _print(vector<vector<T>> v);
template<class T>void _print(stack<T> v);
template<class T>void _print(queue<T> v);
template<class T, class V>void _print(pair<T, V> p);
template<class T>void _print(queue<T> v) {cerr << "[ "; while (!v.empty()) {_print(v.front()); cerr << " "; v.pop();} cerr << " ]";}
template<class T>void _print(stack<T> v) {cerr << "[ "; while (!v.empty()) {_print(v.top()); cerr << " "; v.pop();} cerr << " ]";}
template<class T, class V>void _print(pair<T, V> p) {_print(p.first); cerr << " "; _print(p.second); cerr << nline;}
template<class T>void _print(set<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(vector<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(multiset<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(unordered_set<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T, class V>void _print(map<T, V> v) {cerr << "[ "; for (auto &i : v) {_print(i.first); cerr << " "; _print(i.second); cerr << "\n";} cerr << "]";}
template<class T, class V>void _print(unordered_map<T, V> v) {cerr << "[ "; for (auto &i : v) {_print(i.first); cerr << " "; _print(i.second); cerr << "\n";} cerr << "]";}
template<class T>void _print(vector<vector<T>> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << nline;} cerr << "]";}
/************************************************************************************************************/
/************************************************************************************************************/
/************************************************************************************************************/
ll n,k;
ll sz[N];
bool dead[N];
ll dist[N];
vector<pair<ll, ll>> g[N];
vector<ll> temp;
void prep(int v,ll d, ll len, int par = -1)
{
if(len > k)return;
dist[len] = min(dist[len], d);
temp.push_back(len);
for(auto &val:g[v])
{
if(val.first == par || dead[val.first])continue;
prep(val.first, d + 1, len + val.second, v);
}
}
ll func(int v, ll d, ll len, int par = -1)
{
if(len > k)return INF;
ll ans = d + dist[k - len];
debug(v);
debug(d);
debug(dist[k - len]);
for(auto &val:g[v])
{
if(val.first == par || dead[val.first])continue;
ans = min(ans, func(val.first, d + 1, len + val.second, v));
}
return ans;
}
void dfs(int v, int par=-1)
{
sz[v] = 1;
for(auto &val:g[v])
{
if(val.first != par && !dead[val.first])
{
dfs(val.first, v);
sz[v] += sz[val.first];
}
}
}
int find_centroid(int currSize, int v, int par = -1)
{
for(auto &val:g[v])
if(val.first != par && !dead[val.first] && 2 * sz[val.first] > currSize)
return find_centroid(currSize, val.first, v);
return v;
}
ll decompose(int v)
{
dfs(v);
int centorid = find_centroid(sz[v], v);
dead[centorid] = true;
ll ans = INF;
temp.clear();
dist[0] = 0;
for(auto &val:g[centorid])
{
if(!dead[val.first])
{
ans = min(func(val.first, 1, val.second, centorid), ans);
prep(val.first, 1, val.second, centorid);
}
}
dist[0] = INF;
for(auto &val:temp)
dist[val] = INF;
for(auto &val:g[centorid])
if(!dead[val.first])
ans = min(ans, decompose(val.first));
return ans;
}
void best_path(int nn, int K, int *H[], int* L)
{
n = nn;
k = K;
vector<pair<ll, ll>> arr;
for(int i=0;i<N;i++)
dist[i] = INF;
for(int i=0;i<n-1;i++)
{
ll u,v;
u = H[i][0];
v = H[i][1];
arr.push_back({u,v});
}
int ct = 0;
for(auto &val:arr)
{
ll w;
w = L[ct++];
g[val.first].push_back({val.second, w});
g[val.second].push_back({val.first, w});
}
ll ans = decompose(0);
if(ans >= INF)
cout<<-1<<nline;
else
cout<<ans<<nline;
}