# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
554170 | 2022-04-27T18:29:36 Z | Alma | Traffic (IOI10_traffic) | C++17 | 0 ms | 212 KB |
#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 bestCity = city; ll bestDiff = 1e9, 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; } } 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); arenaCity = 0; untraffic(0); return arenaCity; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |