#include <bits/stdc++.h>
// #include "traffic.h"
using namespace std;
typedef long long int ll;
vector<vector<int>> graph;
vector<ll> cost;
vector<bool> visited;
vector<ll> DP;
int arenaCity;
ll traffic (int city) {
if (DP[city] != -1) return DP[city];
DP[city] = cost[city];
visited[city] = true;
for (int road: graph[city]) {
if (!visited[road]) DP[city] += traffic(road);
}
return DP[city];
}
void untraffic (int city, int cityMaxDiff) {
int bestCity = city;
ll bestDiff = cityMaxDiff, maxCongestion = DP[city];
for (int road: graph[city]) {
// if (DP[road] < maxCongestion) continue;
ll diff = maxCongestion - DP[road];
if (diff < bestDiff) {
bestCity = road;
bestDiff = diff;
}
}
if (bestCity != city) {
DP[city] -= DP[bestCity];
DP[bestCity] = maxCongestion;
arenaCity = bestCity;
ll congestion = 0;
for (auto road: graph[bestCity]) {
congestion = max(congestion, DP[road]);
}
untraffic(bestCity, congestion);
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
graph.assign(N, vector<int>());
cost.clear();
DP.assign(N, -1);
for (int i = 0; i < N; i++) {
graph[S[i]].push_back(D[i]);
graph[D[i]].push_back(S[i]);
cost.push_back(pp[i]);
}
visited.assign(N, false);
ll congestion = traffic(0);
congestion = 0;
for (auto road: graph[0]) {
congestion = max(congestion, DP[road]);
}
arenaCity = 0;
untraffic(0, congestion);
return arenaCity;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |