| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 314746 | jaaguptamme | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define pii pair<ll,ll>
#include "race.h"
using namespace std;
const ll CN=1000005;
vector<pii>g[CN];
map<ll,ll>*mp[CN];
ll dist[CN],sz[CN],dep[CN];
ll res=INT_MAX;
ll k;
void dfs(ll u,ll prev){
sz[u]=1;
ll mxsz=-1,mxn=-1;
for(auto el:g[u]){
ll v=el.first;
ll c=el.second;
if(v==prev)continue;
dist[v]=dist[u]+c;
dep[v]=dep[u]+1;
dfs(v,u);
sz[u]+=sz[v];
if(sz[v]>mxsz){
mxsz=sz[v];
mxn=v;
}
}
if(mxsz!=-1)mp[u]=mp[mxn];
else mp[u]=new map<ll,ll>();
if((*mp[u]).count(dist[u]))(*mp[u])[dist[u]]=min((*mp[u])[dist[u]],dep[u]);
else (*mp[u])[dist[u]]=dep[u];
for(auto E:g[u]){
ll v=E.first;
if(v==prev ||v==mxn)continue;
for(auto el:(*mp[v])){
ll nx=el.first;
ll de=el.second;
if((*mp[u]).count(k-nx)){
ll node=(*mp[u])[k-nx];
res=min(res,abs(de-dep[u])+abs(dep[u]-node));
// cout<<"CHANGE"<<nx<<' '<<k<<' '<<de<<' '<<res<<'\n';
}
}
for(auto el:(*mp[v])){
ll nx=el.first;
ll de=el.second;
if((*mp[u]).count(nx)){
(*mp[u])[nx]=min((*mp[u])[nx],de);
}else (*mp[u])[nx]=de;
}
}
/*
cout<<"NODE";
cout<<u<<' '<<prev<<' '<<dist[u]<<' '<<dep[u]<<'\n';
for(auto el:(*mp[u]))cout<<el.first<<' '<<el.second<<'\n';
*/
if((*mp[u]).count(k+dist[u])){
ll node=(*mp[u])[k+dist[u]];
//cout<<"CHANG"<<k-dist[u]<<' '<<node<<' '<<dep[u]<<' '<<u<<'\n';
res=min(res,abs(node-dep[u]));
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k=K;
for(int i=0;i<N-1;i++){
ll u,v,c;u=H[i][0];
v=H[i][1];
c=L[i];
g[u].push_back({v,c});
g[v].push_back({u,c});
}
for(int i=0;i<CN;i++){
dep[i]=0;
dist[i]=0;
sz[i]=0;
}
dep[1]=0;
dfs(1,N);
int ans=res;
if(ans<=N)return ans;
else return -1;
}
/*
int main(){
int n=4;
int k=7;
int h[][2]={{0,1},{1,2},{1,3}};
int l[]={1,2,4};
std::cout<<best_path(n,k,h,l)<<'\n';
}
*/
/*
int main(){
int n=11;
int k=12;
int h[][2]={{0,1},{0,2},{2,3},{3,4},{4,5},{0,6},{6,7},{6,8},{8,9},{8,10}};
int l[]={3,4,5,4,6,3,2,5,6,7};
cout<<best_path(n,k,h,l)<<'\n';
}
*/