# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
991070 | borisAngelov | Traffic (IOI10_traffic) | C++17 | 4 ms | 31324 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
const long long inf = (1LL << 60);
int n;
int a[maxn];
vector<int> g[maxn];
long long sum = 0;
long long ans = inf;
void dfs(int node, int par, int dep)
{
sum += (1LL * a[node]) * (1LL * dep);
for (int i = 0; i < g[node].size(); ++i)
{
if (g[node][i] != par)
{
dfs(g[node][i], node, dep + 1);
}
}
}
int LocateCentre(int N, int pp[], int S[], int D[])
{
n = N;
for (int i = 1; i <= n; ++i)
{
a[i] = pp[i - 1];
if (i == n)
{
break;
}
int x = S[i - 1];
int y = D[i - 1];
++x;
++y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; ++i)
{
sum = 0;
dfs(i, -1, 0);
ans = min(ans, sum);
}
return ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |