| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 381033 | ponytail | 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;
#ifdef ONLINE_JUDGE
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> OST;
#endif
#define double long double
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
const int MOD = 1000000007;
const int MOD2 = 998244353;
mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 2e5 + 10;
const int is_query = -BIG;
int sz[MAXN], maxsz[MAXN], n, k;
vector<pair<int,int> >adj[MAXN];
unordered_map<int,int> f[MAXN];
const int MAXK = 10000010;
int exist[MAXK], exist2[MAXK];
int ans = 1e9;
int whole_size;
int number_of_operations = 0;
int dfs0(int node,int prev){
sz[node]=1;
number_of_operations++;
for(pair<int,int>x:adj[node]){
if(x.se==-1)continue;
if(x.fi==prev)continue;
int d=dfs0(x.fi,node);
sz[node]+=d;
}
return sz[node];
}
int dfs(int node,int prev){
sz[node]=1;
maxsz[node]=0;
number_of_operations++;
for(pair<int,int> x:adj[node]){
if(x.se==-1) continue;
if(x.fi==prev) continue;
int d=dfs(x.fi,node);
sz[node]+=d;
maxsz[node]=max(maxsz[node],d);
}
maxsz[node]=max(maxsz[node],whole_size-sz[node]);
return sz[node];
}
queue<int>ntv;
vector<int>all;
void wheewhoowhee(int node,int prev){
all.pb(node);
for(pair<int,int>x:adj[node]){
if(x.se==-1)continue;
if(x.fi==prev)continue;
wheewhoowhee(x.fi,node);
}
}
int divide(){
all.clear();
wheewhoowhee(ntv.front(),-1);
for(int i:all){
sz[i]=0;
maxsz[i]=1e9;
number_of_operations++;
}
whole_size=dfs0(ntv.front(),-1);
dfs(ntv.front(),-1);
ntv.pop();
int centroid=0, e=1e9;
for(int i:all){
if(e>maxsz[i]){
e=maxsz[i];
centroid=i;
}
}
for(pair<int,int> x:adj[centroid]){
if(x.se==-1) continue;
ntv.push(x.fi);
}
return centroid;
}
queue<int>used, used2, used3;
void dfs2(int node,int prev,int cur,int dep){
// cout <<cur <<"\n";
if(cur>=1 && cur<MAXK && exist2[cur]==1e9){
// cout << "FUCK\n";
used.push(cur);
used3.push(cur);
}
if(cur>=1 && cur<MAXK){
exist2[cur]=min(exist2[cur],dep);
}
for(pair<int,int>x:adj[node]){
if(x.se==-1) continue;
if(x.fi==prev) continue;
dfs2(x.fi,node,cur+x.se,dep+1);
}
}
void conquer(int root){
while(used2.size()){
exist[used2.front()]=1e9;
used2.pop();
}
for(int i=0;i<adj[root].size();i++){
if(adj[root][i].se==-1) continue;
int sto=adj[root][i].se;
adj[root][i].se=-1;
adj[adj[root][i].fi][f[adj[root][i].fi][root]].se=-1;
dfs2(adj[root][i].fi,-1,sto,1);
while(used3.size()){
// cout << "E "<<i<<" "<<used3.front()<<"\n";
if(k==used3.front()){
ans=min(ans,exist2[used3.front()]);
}
if(k-used3.front()>=1 && k-used3.front()<MAXK && exist[k-used3.front()]!=1e9){
// cout << "F "<<exist[k-used3.front()] << " " << exist2[used3.front()] << "\n";
ans=min(ans,exist[k-used3.front()]+exist2[used3.front()]);
// cout << "G "<<ans << "\n";
}
used3.pop();
}
while(used.size()){
if(exist[used.front()]==1e9) used2.push(used.front());
exist[used.front()]=min(exist[used.front()],exist2[used.front()]);
// cout << "exist "<<used.front()<<" "<<exist[used.front()]<<"\n";
exist2[used.front()]=1e9;
used.pop();
}
}
}
signed best_path(signed N,signed K,signed h[][2],signed l[]){
n=N, k=K;
for(int i=1;i<=n;i++) exist[i]=1e9, exist2[i]=1e9;
for(int i=1;i<n;i++){
int u=h[i-1][0],v=h[i-1][1],w=l[i-1];
//cin >> u >> v >> w;
u++, v++;
int U=adj[u].size();
int V=adj[v].size();
f[u][v]=U;
f[v][u]=V;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
ntv.push(1);
while(ntv.size()){
conquer(divide());
}
return (ans==1e9 ? -1 : ans);
}