| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 429423 | Odavey | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//
// ~oisín~ C++ Template
//
#include <bits/stdc++.h>
#define MX_N 200005
#define mp make_pair
#define mod7 1000000007
#define modpi 314159
#define PI 3.141592653589793238
#define pb push_back
#define FastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define All(a) a.begin(),a.end()
#define fi first
#define se second
#define ll long long int
#define ull unsigned long long int
int kx[8] = {+2, +2, -2, -2, +1, +1, -1, -1};
int ky[8] = {+1, -1, +1, -1, +2, -2, +2, -2};
int d9x[9] = {+1, +1, +1, +0, +0, +0, -1, -1, -1};
int d9y[9] = {+1, +0, -1, +1, +0, -1, +1, +0, -1};
int dx4[4] = {+0, +0, +1, -1};
int dy4[4] = {+1, -1, +0, +0};
ll gcd(ull a, ull b){
return (a==0)?b:gcd(b%a,a);
}
ll lcm(ull a, ull b){
return a*(b/gcd(a,b));
}
const long long INF = 1e18;
using namespace std;
map<ll, bool> d_b;
map<ll, int> d_id;
map<int, int> l_q[MX_N];
ll k;
bool is_heavy[MX_N];
int card[MX_N], p[MX_N], heavy[MX_N], l[MX_N], tin[MX_N], tout[MX_N], whom[MX_N*2];
ll depth[MX_N];
int gl_tit = 0;
int gl_dit = 0;
vector<pair<int, ll> > adj[MX_N];
void info_dfs(int at){
whom[gl_tit] = at;
tin[at] = gl_tit++;
card[at] = 1;
heavy[at] = -1;
is_heavy[at] = false;
for(auto& [to, w] : adj[at]){
if(p[at] == to){
continue;
}
p[to] = at;
l[to] = l[at] + 1;
depth[to] = depth[at] + w;
info_dfs(to);
if(heavy[at] == -1){
heavy[at] = to;
}else{
if(card[to] > card[heavy[at]]){
heavy[at] = to;
}
}
}
if(heavy[at] != -1){
is_heavy[heavy[at]] = true;
}
whom[gl_tit] = -1;
tout[at] = gl_tit++;
return;
}
int ans = 1000000009;
void dfs(int at){
for(auto& [to, w] : adj[at]){
if(to == p[at] || is_heavy[to]){
continue;
}
dfs(to);
}
if(heavy[at] != -1){
dfs(heavy[at]);
}
for(auto& [to, w] : adj[at]){
if(to == p[at] || is_heavy[to]){
continue;
}
for(int i=tin[to];i<=tout[to];++i){
if(whom[i] == -1){
continue;
}
if(d_b[depth[whom[i]]] == false){
l_q[gl_dit][l[whom[i]]]++;
d_id[depth[whom[i]]] = gl_dit++;
d_b[depth[whom[i]]] = true;
}else{
int tmp_it = d_id[depth[whom[i]]];
l_q[tmp_it][l[whom[i]]]++;
}
}
}
if(d_b[depth[at]] == false){
l_q[gl_dit][l[at]]++;
d_id[depth[at]] = gl_dit++;
d_b[depth[at]] = true;
}else{
int tmp_it = d_id[depth[at]];
l_q[tmp_it][l[at]]++;
}
for(auto& [to, w] : adj[at]){
if(to == p[at] || is_heavy[to]){
continue;
}
for(int i=tin[to];i<=tout[to];++i){
if(whom[i] == -1){
continue;
}
int a = whom[i];
ll db = k + 2ll*depth[at] - depth[a];
if(d_b[db] == false){
continue;
}
int tmp_id = d_id[db];
if(l_q[tmp_id].empty()){
continue;
}
int lb = l_q[tmp_id].begin()->first;
if(((lb == l[a]) && (l_q[tmp_id][lb] == 1) && depth[a] == db) || (l_q[tmp_id][lb] == 0)){
continue;
}
//cout << "With god as my witness, a = " << a << ", db & lb = " << db << " & " << lb << ", giving " << l[a] + lb - 2*l[at] << " length(s)\n";
ans = min(ans, l[a] + lb - 2*l[at]);
}
}
if(!is_heavy[at]){
for(int i=tin[at];i<=tout[at];++i){
if(whom[i] == -1){
continue;
}
int tmp_it = d_id[depth[whom[i]]];
l_q[tmp_it][l[whom[i]]]--;
}
}
return;
}
int best_path(int N, int K, int*[2] H, int* L){
for(int i=0;i<N-1;++i){
int u = H[0][i], v = H[1][i];
ll w = L[i];
adj[u].pb({v, w});
adj[v].pb({u, w});
}
k = K;
l[0] = 0;
depth[0] = 0;
info_dfs(0);
dfs(0);
return ans;
}