| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1294487 | cansu_mutlu | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "race.h"
#define int long long
using namespace std;
const int mxn = 2*1e5+5;
vector<vector<array<int,2>>> a(mxn);
vector<array<int,2>> dist(mxn,{0,0});
// dist 0 = kac node gectik, 1 = toplam dist
map<int,int> mp[mxn];
int n,tt;
int ans = 1e18;
void df(int s,int anne,int d)
{
if(anne!=-1)
{
dist[s] = {dist[anne][0]+1,dist[anne][1]+d};
}
for(auto x :a[s])
{
if(x[0]==anne) continue;
df(x[0],s,x[1]);
}
}
void dfs(int s,int anne)
{
for(auto i:a[s])
{
int x = i[0];
if(x==anne) continue;
dfs(x,s);
if(mp[x].size()>mp[s].size())
swap(mp[x],mp[s]);
for(auto x:mp[x])
{
//cout <<s <<" "<< x.first << " "<< dist[s][1] << endl;
if((x.first-dist[s][1])==tt)
{
ans = min(ans,x.second-dist[s][0]);
//cout <<"111111111111111111 " << x.second-dist[s][0] << endl;
}
auto it = mp[s].find(tt-x.first+2*dist[s][1]);
if(it==mp[s].end()) continue;
//cout << x.first << endl;
ans = min(ans,it->second+x.second-2*dist[s][0]);
}
for(auto k:mp[x])
{
if(mp[s].count(k.first)) mp[s][k.first] = min(mp[s][k.first],k.second);
else mp[s][k.first] = k.second;
}
}
if(mp[s].count(dist[s][1])) mp[s][dist[s][1]] = min(mp[s][dist[s][1]],dist[s][0]);
else mp[s][dist[s][1]] = dist[s][0];
auto it = mp[s].find(tt+dist[s][1]);
if(it!=mp[s].end())
{
ans = min(ans,it->second-dist[s][0]);
}
}
int best_path(int n, int k, int h[][2], int l[])
{
for(int i=0;i<n-1;i++)
{
a[h[i][0]].push_back({h[i][1],l[i]});
a[h[i][1]].push_back({h[i][0],l[i]});
}
tt = k;
df(0,-1,-1);
//for(int i=1;i<=n;i++) cout << i << " "<< dist[i][0] <<" " << dist[i][1] << endl;
dfs(0,-1);
//for(auto k:mp[1]) cout << k.first << " "<< k.second << endl;
//cout << ans << endl;
if(ans==1e18) return -1;
return ans;
}