| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 450864 | joshjms | Traffic (IOI10_traffic) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "traffic.h"
#include <bits/stdc++.h>
#define KON using
#define AQUA namespace std;
KON AQUA
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x) cout << #x << " => " << x << "\n";
#define sp " "
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
const int inf = 0x3f3f3f3f;
const int INFF = 1e18 + 5;
const int INF = 1e10 + 5;
const int MX = 3e5 + 5;
const int MXL = 105;
const int mod = 1e9 + 7;
const double ERROR = 1e-5;
int arr[MX], max_cong[MX], total;
pair <int,int> ans = {INFF, INFF};
vector <int> E[MX];
bool vis[MX];
int dfs(int pos){
int sum = arr[pos], res = 0;
for(auto i:E[pos]){
if(vis[i]) continue;
vis[i] = 1;
int ret = dfs(i);
res = max(res, ret);
sum += ret;
}
res = max(res, total - sum);
max_cong[pos] = res;
return sum;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for(int i = 0; i < N; i++){
arr[i] = pp[i];
total += arr[i];
}
for(int i = 0; i < N - 1; i++){
E[S[i]].pb(D[i]);
E[D[i]].pb(S[i]);
}
vis[0] = 1;
dfs(0);
for(int i = 0; i < N; i++)
ans = min(ans, {max_cong[i], i});
return ans.se;
}
/*
static int N,P[1000000],S[1000000],D[1000000];
int32_t main(){
int i;
scanf("%d",&N);
for (i=0;i<N;i++) scanf("%d",&P[i]);
for (i=0;i<N-1;i++) scanf("%d%d",&S[i],&D[i]);
int r = LocateCentre(N,P,S,D);
printf("%d\n",r);
return 0;
}
*/