oj.uz

Submission #363040

# Submission time Handle Problem Language Result Execution time Memory
363040 2021-02-05T03:23:07 Z nishuz Traffic (IOI10_traffic) C++14
0 / 100
 52 ms 48108 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAX = 1e6 + 1;
vector <int> adj[MAX];
ll sum[MAX];
int pars[MAX];

void dfs(int u, int par, int p[])
{
    sum[u] = p[u];
    pars[u] = par;
    for (int v : adj[u])
        if (v != par)
            dfs(v, u, p);
    for (int v : adj[u])
        if (v != par)
            sum[u] += sum[v];
}

int LocateCentre(int n, int p[], int s[], int d[])
{
    for (int i = 0; i < n - 1; ++i)
    {
        adj[s[i]].emplace_back(d[i]);
        adj[d[i]].emplace_back(s[i]);
    }
    dfs(0, 0, p);
    pair <ll, int> ans = make_pair(LLONG_MAX, -1);
    for (int u = 0; u < n; ++u)
    {
        ll m = -1, cur = p[u];
        for (int v : adj[u])
        {
            if (v != pars[u])
            {
                m = max(m, sum[u]);
                cur += p[v];
            }
        }
        if (u) m = max(m, sum[0] - cur);
        ans = min(ans, make_pair(m, u));
    }
    cout << ans.second << '\n';
}

Compilation message

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:48:1: warning: no return statement in function returning non-void [-Wreturn-type]
   48 | }
      | ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 48108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 48108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 48108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 48108 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -