| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 330508 | nicolaee3 | Traffic (IOI10_traffic) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
ifstream fin("milkvisits.in");
ofstream fout("milkvisits.out");
#define NMAX 1000005
typedef long long ll;
vector<int> v[NMAX];
ll val[NMAX];
ll P[NMAX];
ll minim = (1<<30);
ll dfs(int nod,int tata)
{
val[nod] = P[nod];
for(auto u : v[nod])
{
if(u != tata)
{
dfs(u,nod);
val[nod] += val[u];
}
}
}
void dfs2(int nod,int tata)
{
ll maxim = val[0] - val[nod];
for(auto u : v[nod])
{
if(u != tata)
{
maxim = max(maxim,val[u]);
}
}
//cout<<nod<<" "<<maxim<<endl;
minim = min(minim,maxim);
for(auto u : v[nod])
{
if(u != tata)
{
dfs2(u,nod);
}
}
}
int LocateCentre(int n,ll p[],ll s[],ll d[])
{
for(int i=0;i<=n-2;i++)
{
int a = s[i];
int b = d[i];
v[a].push_back(b);
v[b].push_back(a);
}
for(int i=0;i<=n-1;i++)
P[i] = p[i];
dfs(0,-1);
dfs2(0,-1);
return minim;
}
/*
int main()
{
ll p[NMAX],s[NMAX],d[NMAX];
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>p[i];
}
for(int i=0;i<=n-2;i++)
{
int a,b;
cin>>s[i]>>d[i];
}
cout<<LocateCentre(n,p,s,d);
}
5
10 10 10 20 20
0 2
1 2
2 3
3 4
*/