# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
347930 | 2021-01-13T19:52:32 Z | training4usaco | Traffic (IOI10_traffic) | C++11 | 2 ms | 492 KB |
#include "traffic.h" #include <climits> #include <iostream> #include <vector> using namespace std; int n; vector<int> p; vector<vector<int>> adj; vector<int> traffic; vector<int> children; int numFans = 0; void dfs (int idx, int par) { for (int i = 0; i < adj[idx].size(); ++i) { if (adj[idx][i] == par) { continue; } dfs(adj[idx][i], idx); children[idx] += children[adj[idx][i]]; traffic[idx] = max(traffic[idx], children[adj[idx][i]]); } traffic[idx] = max(traffic[idx], numFans - children[idx] - p[idx]); children[idx] += p[idx]; } int LocateCentre (int ni, int pi[], int d[], int s[]) { n = ni; for(int i = 0; i < n; ++i) { p[i] = pi[i]; } adj = vector<vector<int>>(n); traffic = vector<int>(n); children = vector<int>(n); for (int i = 0; i < n; i++) { numFans += p[i]; } for (int i = 0; i < n - 1; i++) { adj[s[i]].push_back(d[i]); adj[d[i]].push_back(s[i]); } dfs(0, -1); int best = INT_MAX; int ans = -1; for (int i = 0; i < n; i++) { if (traffic[i] < best) { ans = i; best = traffic[i]; } } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 2 ms | 492 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |