| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 499554 | iwantin | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define M_PI 3.14159265358979323846
#define pb push_back
#define fs first
#define sc second
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;
const ll maxn = 1e5 + 1;
const ll inf = LLONG_MAX;
const ll minf = LLONG_MIN;
ll cost[maxn * 10], dist[maxn * 10],
children[maxn * 10], ans[maxn * 10];
vector <vector <ll> > g(maxn * 10);
bool used[maxn * 10];
ll n;
ll findChildren(ll v){
used[v] = true;
children[v] = 1;
for(auto i: g[v])
if(!used[i])
children[v] += findChildren(i);
return children[v];
}
ll findDist(ll v){
used[v] = true;
ll isZero = !(v == 0), num = 0;
ans[0] += cost[v] * children[v] * isZero;
for(auto i: g[v])
if(!used[i])
num += findDist(i);
dist[v] = num + cost[v] * children[v] * isZero;
return dist[v];
}
void findAns(ll v, ll parent = -1){
used[v] = true;
if(parent != -1){
ans[v] = cost[parent] * (n - children[parent] + 1) + ans[parent];
ans[v] -= cost[v] * (children[v]);
}
for(auto i: g[v])
if(!used[i])
findAns(i, v);
}
void workYouPieceOfShit(){
cin>>n;
for(ll k = 0; k < n; k++)
cin>>cost[k];
for(ll k = 0; k < n - 1; k++){
ll a, b; cin>>a>>b;
g[a].pb(b);
g[b].pb(a);
}
findChildren(0);
for(ll k = 0; k < n; k++)
used[k] = false;
findDist(0);
for(ll k = 0; k < n; k++)
used[k] = false;
findAns(0);
ll mn = LLONG_MAX, ansk = 0;
for(ll k = 0; k < n; k++){
if(ans[k] < mn){
mn = ans[k];
ansk = k;
}
}
cout<<ansk;
}
int main(){
int t = 1; //cin>>t;
while(t--){
workYouPieceOfShit();
}
return 0;
}