| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 479431 | kamalsharmaa9 | Race (IOI11_race) | C++14 | 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.
//https://pastebin.com/jVURaNCJ
#include<bits/stdc++.h>
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define N 100005
#define ff first
#define ss second
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define inf 1e18
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define w(x) int x; cin>>x; while(x--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void c_p_c()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
vector<int>gr[N];
map<int, map<int, int>>edge;
map<int, int>m[N];
int depth[N];
int fin_ans = inf;
int k;
pair<int, int> dfs(int node, int par)
{
///cout << node << "++";
map<int, int>d_val;
int sz = 0;
int ind;
for (auto child : gr[node])
{
// cout << child << endl;
if (child != par )
{
//cout << child << endl;
pii temp = dfs(child, node);
if (temp.ss > sz)
{
sz = temp.second;
ind = child;
}
d_val[child] = temp.ff;
}
}
if (sz == 0) {
// it is a leaf node
m[node][0] = 1;
return {0, 1};
}
//
////.. find answer in this subtree like the greatest one
//
//int to_find = k - edge[node][ind];
for (auto child : gr[node])
{
if (child == par)
continue;
int to_find = k - edge[node][child];
if (to_find == 0)
fin_ans = 1;
if (child != par)
{
if (m[child].find(to_find) != m[child].end())
{
fin_ans = min(fin_ans, 2 + d_val[child] - m[child][to_find]);
}
}
}
m[node].swap(m[ind]); int d = d_val[ind] + 1;
m[node][edge[node][ind]] = d;
for (auto child : gr[node])
{
if (child != par && child != ind)
{
// go in this
for (auto i : m[child])
{
int val = i.first + edge[node][child];
int to_find = k - val;
if (to_find == 0)
fin_ans = min(fin_ans, d_val[child] - i.ss + 1);
if (m[node].find(to_find) != m[node].end())
{
// cout << node << " " << to_find << " " << d_val[child] << " " << m[child][i.ff] << endl;
fin_ans = min(fin_ans, d - m[node][to_find] + 1 + d_val[child] - m[child][i.ff] + 1);
}
if (m[node].find(i.first) != m[node].end() && (d - m[node][i.first]) < (d_val[child] - m[child][i.first] + 1))
m[node][i.ff] = d;
else
m[node][i.ff] = d;
}
}
}
// cout << node << " " << fin_ans << endl;
return {d, m[node].size()};
}
int best_path(int N,int K,int H[][2],int L[]){
int i,j,a,b,c,n;
//scanf("%lld%lld",&n,&l);
n=N;k=K;
for(i=0;i<n-1;i++){
//scanf("%lld%lld%lld",&a,&b,&c);
//a++;b++;
a=H[i][0];b=H[i][1];c=L[i];
a++;b++;
edge[a][b] = c;
edge[b][a] = c;
gr[a].pb(b);
gr[b].pb(a);
}
dfs(1,0);
return fin_ans;
}