| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 524846 | antonioqbab | Traffic (IOI10_traffic) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int LocateCentre(int n, int p[], int s[], int d[]){
vector<vector<int>> G(n);
for(int i=0;i<n-1;++i){
G[s[i]].emplace_back(d[i]);
G[d[i]].emplace_back(s[i]);
}
vector<ll> dp(n), dp2(n);
// dp[node][edge] (max excluding edge)
function<void(int,int)> dfs=[&](int node, int last){
ll cur = 0;
for(auto x:G[node])
if(x!=last){
dfs(x,node);
cur=max(cur,dp[x]);
}
dp[node]=cur+p[node];
};
dfs(0,-1);
ll ans = dp[0] - p[0];
dp2[0]=dp[0];
//cout << ans << '\n';
function<void(int,int)> dfs2=[&](int node, int last){
ans = min(ans, dp2[node]-p[node]);
//cout << node << ' ' << dp[node] << ' ' << dp2[node] << '\n';
for(auto x:G[node])
if(x!=last){
dp2[x]=max(dp[x],dp2[node]+p[x]);
dfs2(x,node);
}
};
dfs2(0,-1);
return ans;
}
int main(){
int n = 5;
int *p=new int[n], *s=new int[n], *d=new int [n];
p[0]=p[1]=p[2]=10;
p[3]=p[4]=20;
s[0]=0,d[0]=2;
s[1]=1,d[1]=2;
s[2]=2,d[2]=3;
s[3]=3,d[3]=4;
cout << LocateCentre(n,p,s,d);
}