| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 405092 | Vladth11 | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
#include"race.h"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
const ll NMAX = 200001;
const ll INF = (1LL << 60);
const ll MOD = 1000000009;
const ll BLOCK = 225;
const ll base = 31;
const ll base2 = 53;
const ll nr_of_bits = 21;
vector <pii> v[NMAX];
int best = 2e9;
int k;
int sz[NMAX];
int total;
int viz[NMAX];
int d[NMAX];
vector <pii> mp[1000001];
void getsize(int node, int p){
sz[node] = 1;
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
getsize(node, x.first);
sz[node] += sz[x.first];
}
total = sz[node];
}
int centroid(int node, int p){
for(auto x : v[node]){
if(viz[x.first] || x.first == p){
continue;
}
if(sz[x.first] > total / 2)
return centroid(x.first, node);
}
return node;
}
int OneCentroid(int node){
getsize(node, 0);
return centroid(node, 0);
}
void ComputeDist(int node, int p, int subTree, int dist, int level){
d[node] = dist;
pii act = {level, subTree};
if(dist <= k && (!mp[dist].size() || mp[dist].back().first >= level))
mp[dist].push_back(act);
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
ComputeDist(x.first, node, subTree, d[node] + x.second, level + 1);
}
}
void SuperErase(int node, int p, int subTree, int level){
int dist = d[node];
pii act = {level, subTree};
if(dist <= k){
mp[dist] = {(int)2e9, -1, (int)2e9, -1};
}
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
SuperErase(x.first, node, subTree, level + 1);
}
}
void Erase(int node, int p, int subTree, int level){
int dist = d[node];
pii act = {level, subTree};
if(dist <= k && (mp[dist].size() && mp[dist].back() == act))
mp[dist].pop_back();
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
Erase(x.first, node, subTree, level + 1);
}
}
void Add(int node, int p, int subTree, int level){
int dist = d[node];
pii act = {level, subTree};
if(dist <= k && (!mp[dist].size() ||mp[dist].back().first >= level))
mp[dist].push_back(act);
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
Add(x.first, node, subTree, level + 1);
}
}
void Compute(int node, int p, int level){
int trb = k - d[node];
if(trb >= 0 && mp[trb].size() != 0)
{
int b = mp[trb].back().first;
best = min(best, b + level);
}
for(auto x : v[node]){
if(x.first == p || viz[x.first])
continue;
Compute(x.first, node, level + 1);
}
}
void CD(int node){
int c = OneCentroid(node);
viz[c] = 1;
for(int i = 0; i <= k; i++)
mp[i].clear();
mp[0].push_back({0, 0});
for(auto x : v[c]){
if(viz[x.first])
continue;
ComputeDist(x.first, c, x.first, x.second, 1);
}
for(auto x : v[c]){
if(viz[x.first])
continue;
Erase(x.first, c, x.first, 1);
Compute(x.first, 0, 1);
Add(x.first, c, x.first, 1);
}
for(auto x : v[c]){
if(viz[x.first])
continue;
SuperErase(x.first, c, x.first, 1);
}
for(auto x : v[c]){
if(viz[x.first])
continue;
CD(x.first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for(int i = 0; i < N - 1; i++){
int a = H[i][0] + 1;
int b = H[i][1] + 1;
v[a].push_back({b, L[i]});
v[b].push_back({a, L[i]});
}
for(int i = 0; i <= k; i++)
mp[i].clear();
CD(1);
if(best == 2e9)
best = -1;
return best;
}