| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 672097 | vjudge1 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include<bits/stdc++.h>
#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
#define int ll
#define Drakon ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 200005, LOG = 25, M = 2;
typedef array<array<int, M>, M> matrix;
int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}
int lcm(int a, int b) {
return (a * b) / __gcd(a, b);
}
int n,k,sz[N];
vector<pair<int,int>>adj[N];
bool vis[N];
void dfs_sz(int u,int p){
sz[u] = 1;
for(auto x:adj[u]){
if(x.first == p || vis[x.first])continue;
dfs_sz(x.first,u);
sz[u] += sz[x.first];
}
}
int dfs_centroid(int u,int p,int s){
for(auto x:adj[u]){
if(x.first == p || vis[x.first])continue;
if(sz[x.first]>s/2)
return dfs_centroid(x.first,u,s);
}
return u;
}
int ans;
int best[1000005];
vector<pair<int,int>>pool;
void dfs(int u,int p,int sum,int dep){
pool.pp({dep,sum});
for(auto v:adj[u]){
if(v.first == p||vis[v.first])continue;
dfs(v.first,u,sum+v.second,dep+1);
}
}
void build_centroid(int u,int p){
dfs_sz(u,p);
int centroid = dfs_centroid(u,p,sz[u]);
vis[centroid] = true;
vector<int>all;
best[0] = 0;
all.pp(0);
for(auto v:adj[centroid]){
if(vis[v.first])continue;
pool.clear();
dfs(v.first,centroid,v.second,1);
for(auto x:pool){
all.pp(x.second);
if(x.second <= k){
if(~best[k-x.second]){
ans = min(ans,x.first+best[k-x.second]);
}
}
}
for(auto x:pool){
if(!~best[x.second]){
best[x.second] = x.first;
}
else{
best[x.second] = min(best[x.second],x.first);
}
}
}
for (auto x:all) {
best[x] = -1;
}
for(auto v:adj[centroid]){
if(vis[v.first])continue;
build_centroid(v.first,centroid);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
n = N,k = K;
for (int i = 0; i < n-1; ++i) {
int u = H[i][0],v = H[i][1],z = L[i];
adj[u].pp({v,z});
adj[v].pp({u,z});
}
ans = INT_MAX;
memset(best,-1,sizeof best);
build_centroid(0,0);
if(ans == INT_MAX)
ans = -1;
return ans;
}