| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1107463 | SoMotThanhXuan | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define left _________left
#define right _________right
#define NAME ""
const int mod = 1e9 + 7;
bool maximize(int &u, int v){
if(v > u){
u = v;
return true;
}
return false;
}
bool minimize(int &u, int v){
if(v < u){
u = v;
return true;
}
return false;
}
bool maximizell(long long &u, long long v){
if(v > u){
u = v;
return true;
}
return false;
}
bool minimizell(long long &u, long long v){
if(v < u){
u = v;
return true;
}
return false;
}
int fastPow(int a, int n){
if(n == 0) return 1;
int t = fastPow(a, n >> 1);
t = 1ll * t * t % mod;
if(n & 1) t = 1ll * t * a % mod;
return t;
}
void add(int &u, int v){
u += v;
if(u >= mod) u -= mod;
}
void sub(int &u, int v){
u -= v;
if(u < 0) u += mod;
}
const int maxN = 2e5 + 5;
const int maxK = 1e6 + 5;
const int INF = 1e9;
vector<pair<int, int>> adj[maxN];
int n, m, k;
int answer = INF, sz[maxN], in[maxN], out[maxN], timeDFS, id[maxN], heavy[maxN], depth[maxN];
int high[maxN];
map<int, int> Min;
inline void dfs(int u){
in[u] = ++timeDFS;
id[timeDFS] = u;
sz[u] = 1;
for(auto[v, w] : adj[u]){
if(in[v])continue;
high[v] = high[u] + 1;
depth[v] = depth[u] + w;
dfs(v);
sz[u] += sz[v];
if(sz[v] > sz[heavy[u]]) heavy[u] = v;
}
out[u] = timeDFS;
}
inline void hld(int u = 1, int pre = 0, bool keep = true){
for(auto[v, w] : adj[u])if(v != heavy[u] && v != pre){
hld(v, u, false);
// cout << "erase ";
// cout << v << "\n";
FOR(i, in[v], out[v]){
// cout << id[i] << ' ' << depth[id[i]] << "\n";
Min.erase(depth[id[i]]);
}
}
if(heavy[u]) hld(heavy[u], u, true);
if(Min.find(depth[u]) == Min.end()) Min[depth[u]] = high[u];
else minimize(Min[depth[u]], high[u]);
// cout << u << "\n";
// cout << answer << ' ';
if(Min.find(k + depth[u]) != Min.end()) minimize(answer, Min[depth[u] + k] - high[u]);
// cout << answer;
// cout << "\n";
for(auto[v, w] : adj[u]){
if(v != heavy[u] && v != pre){
FOR(i, in[v], out[v]){
int c = id[i], tmp = depth[c] - 2 * depth[u];
if(Min.find(k - tmp) != Min.end()){
// cout << u << ' ' << c << " " << depth[c] << ' ' << depth[u] << ' ' << tmp << '\n';
// cout << Min[k - tmp] << "\n";
// cout << answer << ' ';
minimize(answer, high[c] - 2 * high[u] + Min[k - tmp]);
// cout << answer << "\n";
}
}
FOR(i, in[v], out[v]){
if(Min.find(depth[id[i]]) == Min.end()) Min[depth[id[i]]] = high[id[i]];
else minimize(Min[depth[id[i]]], high[id[i]]);
}
}
}
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
for(int i = 0; i < n; ++i){
int u = H[i][0], v = H[i][1], w = L[i];
++u;
++v;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dfs(1);
hld();
return answer == INF ? -1 : answer;
}
//int H[maxN][2], L[maxN];
//inline void solve(){
// cin >> n >> k;
// FOR(i, 1, n - 1){
// int u, v, w;
// cin >> u >> v >> w;
// H[i][0] = u;
// H[i][1] = v;
// L[i] = w;
//
// }
// cout << best_path(n, k, H, L);
//}
//int main(){
// if(fopen(NAME".inp", "r")){
// freopen(NAME".inp", "r", stdin);
// freopen(NAME".out", "w", stdout);
// }
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
//
// int t = 1;
//// cin >> t;
// while(t--){
// solve();
// }
// return 0;
}