# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
647698 | Marceantasy | 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 <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define ar array
const int mxN = 2e5+5, M = 1e9+7;
int n, k, sz[mxN], mxtree[mxN], ans;
vector<pair<int, int>> adj[mxN];
vector<int> new_vis;
bool used[mxN];
int dfs(int u, int p = -1){
sz[u] = 1;
for(pair<int, int> v : adj[u]){
if(v.second != p && !used[v.second]){
sz[u] += dfs(v.second, u);
}
}
return sz[u];
}
int get_centroid(int u, int ms, int p = -1){ // u = node, ms = size of the current tree delimited by previous centroids, p = parent
for(pair<int, int> v : adj[u]){
if(v.second != p && !used[v.second]){
if(sz[v.second]*2 > ms){
return get_centroid(v.second, ms, u);
}
}
}
return u;
}
int flag[mxN], stamp[mxN];
int timestamp;
void solve(int u){
++timestamp;
int sz_curr_tree = dfs(u);
int centroid = get_centroid(u, sz_curr_tree);
used[centroid] = 1;
flag[0] = 0;
stamp[0] = timestamp;
// do something with the centroid
for(pair<int, int> v : adj[centroid]){
if(used[v.second]) continue;
if(v.first > k) continue;
queue<int> q, d, p, l;
vector<int> cd1, cd2;
q.push(v.second);
d.push(v.first);
l.push(1);
p.push(centroid);
while(q.size()){
int qf = q.front();
int df = d.front();
int lf = l.front();
int pf = p.front();
cd1.push_back(df);
cd2.push_back(lf);
if(stamp[k-df] == timestamp) ans = min(flag[k-df] + lf, ans);
q.pop();
d.pop();
l.pop();
p.pop();
for(pair<int, int> v2 : adj[qf]){
int pos = v2.second;
if(used[pos] || pos == pf) continue;
if(df+v2.first > k) continue;
q.push(v2.second);
d.push(df+v2.first);
l.push(lf+1);
p.push(qf);
}
}
for(int i = 0; i<cd1.size(); ++i){
if(stamp[cd1[i]] != timestamp){
flag[cd1[i]] = cd2[i];
stamp[cd1[i]] = timestamp;
}else{
flag[cd1[i]] = min(flag[cd1[i]], cd2[i]);
}
}
}
for(pair<int, int> v : adj[centroid]){
if(used[v.second]) continue;
solve(v.second);
}
// end that something with the centroid xdd
}
int best_path(int N, int K, int H[][2], int L[]){
n = N; k = K;
for(int i = 0; i<N-1; ++i){
adj[H[i][0]].push_back({L[i], H[i][1]});
adj[H[i][1]].push_back({L[i], H[i][0]});
}
ans = (int)1e8;
solve(0);
if(ans > 1e8) return -1;
return ans;
}
/*
int main(){
int _N, _K;
cin >> _N >> _K;
int _H[_N][2], _L[_N];
for(int i = 0; i<_N-1; ++i){
cin >> _H[i][0] >> _H[i][1];
}
for(int i = 0; i<_N-1; ++i){
cin >> _L[i];
}
cout << best_path(_N, _K, _H, _L) << "\n";
}
*/
//https://oj.uz/problem/view/IOI11_race