Submission #365442

#	Time	Username	Problem	Language	Result	Execution time	Memory
365442		alexyd88	Traffic (IOI10_traffic)	C++14	0 / 100	5099 ms	23916 KiB

traffic

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vii vector<pair<int, int>>
#define vvb vector<vector<bool>>
#define piii pair<int, pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define inf INT_MAX
#define pb push_back
#define p push
#define ll long long
#define ull unsigned long long
#define g get
#define dbl double
#define mn 1000005

int N, P[mn];
vi adj[mn];
int fans;
int ans[mn];

int dfs (int loc, int par)
{
    int sb = 0, mb = 0;
    for (auto i : adj[loc])
        if (i != par)
            sb += dfs(i, loc), mb = max(mb, dfs(i, loc));
    ans[loc] = max(mb, fans - sb - P[loc]);
    return sb + P[loc];
}

int LocateCentre(int fN, int fP[mn], int S[mn], int D[mn])
{
    N = fN;
    for (int i = 0; i < N; i++)
        P[i] = fP[i], fans += P[i];
    for (int i = 0; i < N - 1; i++)
        adj[S[i]].pb({D[i]}), adj[D[i]].pb({S[i]});
    dfs(0, -1);
    int bc = inf, bl;
    for (int i = 0; i < N; i++)
        if (bc > ans[i])
            bc = ans[i], bl = i;
    return bl;
}

/*int main(void)
{
    cout << "TR" << endl;
    int N, P[mn], S[mn], D[mn];
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> P[i];
    for (int i = 0; i < N - 1; i++)
        cin >> S[i];
    for (int i = 0; i < N - 1; i++)
        cin >> D[i];
    cout << LocateCentre(N, P, S, D);
}*/

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:51:12: warning: 'bl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |     return bl;
      |            ^~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25