Submission #491345

#	Time	Username	Problem	Language	Result	Execution time	Memory
491345		Alexandruabcde	Traffic (IOI10_traffic)	C++14	100 / 100	981 ms	174632 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"

using namespace std;

constexpr int NMAX = 1e6 + 5;

vector <int> G[NMAX];
int valMax[NMAX];

int sp[NMAX];
int Max[NMAX];
int Dad[NMAX];

void Dfs (int Node, int dad = -1) {
    Dad[Node] = dad;
    for (auto it : G[Node]) {
        if (it == dad) continue;

        Dfs(it, Node);
        sp[Node] += sp[it];
        Max[Node] = max(Max[Node], sp[it]);
    }
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    int Total = 0;
    for (int i = 0; i < N; ++ i ) {
        sp[i] = pp[i];
        Total += pp[i];
    }

    for (int i = 0; i < N-1; ++ i ) {
        G[S[i]].push_back(D[i]);
        G[D[i]].push_back(S[i]);
    }

    Dfs(0);

    int Min = Total+1;
    int poz = -1;
    for (int i = 0; i < N; ++ i ) {
        int val = Max[i];
        val = max(val, Total - sp[i]);

        if (val < Min) {
            Min = val;
            poz = i;
        }
    }

    return poz;
}

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