oj.uz

Submission #848543

# Submission time Handle Problem Language Result Execution time Memory
848543 2023-09-12T21:04:12 Z toma_ariciu Traffic (IOI10_traffic) C++17
0 / 100
 6 ms 30044 KB 
#include <vector>

using namespace std;

const int maxN = 1000005;
int n, sz[maxN], bestDiff, bestCity, total;
vector <int> G[maxN];

void dfs(int nod, int tata) {
    int currDiff = 0;
    for (int vecin : G[nod]) {
        if (vecin == tata) {
            continue;
        }
        dfs(vecin, nod);
        sz[nod] += sz[vecin];
        currDiff = max(currDiff, sz[vecin]);
    }
    currDiff = max(currDiff, total - sz[nod]);
    if (currDiff < bestDiff) {
        bestDiff = currDiff;
        bestCity = nod;
    }
}

int LocateCentre(int N, int P[], int S[], int D[]) {
    n = N;
    for (int i = 1; i <= n; i++) {
        sz[i] += P[i];
        total += P[i];
    }
    bestDiff = 2 * maxN;
    for (int i = 1; i < n; i++) {
        G[S[i]].push_back(D[i]);
        G[D[i]].push_back(S[i]);
    }
    dfs(1, 0);
    return bestCity;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 30040 KB Output is correct
2 Incorrect 6 ms 30044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 30040 KB Output is correct
2 Incorrect 6 ms 30044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 30040 KB Output is correct
2 Incorrect 6 ms 30044 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 30040 KB Output is correct
2 Incorrect 6 ms 30044 KB Output isn't correct
3 Halted 0 ms 0 KB -