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"
//# pragma GCC optimize("Ofast,no-stack-protector")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
/*
# include <ext/pb_ds/tree_policy.hpp>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/rope>
*/
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
# define int ll
using namespace std;
int dep[1 << 17],dep2[1 << 17],s[1 << 17],x,ans = 1e18,n,k;
vector<pair<int,int>>vec[1 << 17];
map<int,multiset<int>>ms;
void pre(int nod,int par,int val)
{
dep[nod] = dep[par] + val;
dep2[nod] = dep2[par] + 1;
s[nod] = 1;
for(auto it : vec[nod])
{
if(it.first != par)
{
pre(it.first,nod,it.second);
s[nod] += s[it.first];
}
}
}
void add1_node(int nod,int gg)
{
if(sz(ms[2 * gg + k - dep[nod]]))
{
x = min(x,dep2[nod] + *(ms[2 * gg + k - dep[nod]].begin()));
}
}
void add2_node(int nod,int gg)
{
ms[dep[nod]].insert(dep2[nod]);
}
void add1(int nod,int par,int gg)
{
add1_node(nod,gg);
for(auto it : vec[nod])
{
if(it.first != par)
{
add1(it.first,nod,gg);
}
}
}
void add2(int nod,int par,int gg)
{
add2_node(nod,gg);
for(auto it : vec[nod])
{
if(it.first != par)
{
add2(it.first,nod,gg);
}
}
}
void del_node(int nod)
{
ms[dep[nod]].erase(ms[dep[nod]].find(dep2[nod]));
}
void del(int nod,int par)
{
del_node(nod);
for(auto it : vec[nod])
{
if(it.first != par)
{
del(it.first,nod);
}
}
}
void dfs(int nod,int par,bool keep)
{
pair<int,int>mx = mp(-1,-1);
for(auto it : vec[nod])
{
if(it.first != par)
{
mx = max(mx,mp(s[it.first],it.first));
}
}
for(auto it : vec[nod])
{
if(it.first != par && it.first != mx.second)
{
dfs(it.first,nod,0);
}
}
if(mx.second != -1) dfs(mx.second,nod,1);
x = 1e18;
add1_node(nod,dep[nod]);
add2_node(nod,dep[nod]);
for(auto it : vec[nod])
{
if(it.first != par && it.first != mx.second)
{
add1(it.first,nod,dep[nod]);
add2(it.first,nod,dep[nod]);
}
}
//cout << nod << ' ' << x << ' ' << x - 2 * dep2[nod] << '\n';
if(x != 1e18) ans = min(ans,x - 2 * dep2[nod]);
if(keep) return ;
del(nod,par);
}
# undef int
int best_path(int N, int K, int H[][2], int L[])
{
# define int ll
k = K;
n = N;
for(int i = 0;i < n - 1;i++)
{
vec[H[i][0]].pb(mp(H[i][1],L[i]));
vec[H[i][1]].pb(mp(H[i][0],L[i]));
}
pre(0,0,0);
dfs(0,0,1);
if(ans == 1e18) return -1;
else return ans;
}
Compilation message (stderr)
race.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
# pragma GCC optimization ("unroll-loops")
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |