| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 860996 | KK_1729 | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long long double
#define pb push_back
#define str string
#define vi vector<int>
#define mp make_pair
#define mi map<int, int>
#define umi unordered_map<int, int>
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define all(a) a.begin(), a.end()
// #define endl "\n"
vector<vector<int>> graph;
vector<int> a;
vector<int> dp;
int calc(int x, int p = -1){
if (dp[x]) return dp[x];
int ans = a[x];
for (auto item: graph[x]){
if (item == p) continue;
ans += calc(item, x);
}
return dp[x] = ans;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
int n = N;
graph.resize(n);
a.resize(n);
int o = 0;
FOR(i,0,n) a[i] = pp[i];
for (auto x: a) o += x;
dp.resize(n);
FOR(i,0,n-1){
int u = S[i];
int v = D[i];
graph[u].pb(v);
graph[v].pb(u);
}
// cout << "i" << endl;
stack<int> s;
s.push(0);
vector<int> visited(n);
// cout << "i" << endl;
calc(0);
// cout << "i" << endl;
vector<int> ans(n);
while (!s.empty()){
int current = s.top();
s.pop();
if (visited[current]) continue;
int m = 0;
int u = 0;
for (auto x: graph[current]){
if (visited[x]) continue;
// parent[x] = current;
m = max(m, dp[x]);
u += dp[x];
s.push(x);
// if (current == 1) cout << x << endl;
}
// if (current == 1) cout << u << endl;
ans[current] = max(m, o-u-a[current]);
visited[current] = 1;
}
// cout << "i" << endl;
int best = 1e10;
int x = 0;
// printVector(ans);
FOR(i,0,n){
if (ans[i] < best){
best = ans[i];
x = i;
// cout << i << endl;
}
}
// printVector(dp);
return x;
}