oj.uz

Submission #764267

# Submission time Handle Problem Language Result Execution time Memory
764267 2023-06-23T09:48:12 Z Blagoj Traffic (IOI10_traffic) C++17
0 / 100
 13 ms 23764 KB 
#include <bits/stdc++.h>
#include "traffic.h"

#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

vector<int> g[1000003];
int sz[1000003], ppl[1000003];
bool visited[1000003];

void dfs(int n, int p = -1) {
    sz[n] = ppl[n];
    for (auto x : g[n]) {
        if (x == p) continue;
        dfs(x, n);
        sz[n] += sz[x];
    }
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    for (int i = 0; i < N - 1; i++) g[S[i]].push_back(D[i]);
    for (int i = 0; i < N; i++) ppl[i] = pp[i];
    dfs(0);
    queue<pair<int, int>> q;
    q.push({0, 0});
    visited[0] = 1;
    ll best = LLONG_MAX, id = 0;
    while (q.size() > 0) {
        int place = q.front().first, sum = q.front().second, cnt = 0, mx = sum;
        q.pop();
        for (auto x : g[place]) {
            if (visited[x]) continue;
            mx = max(mx, sz[x]);
            cnt += sz[x];
        }
        if (mx < best) {
            best = mx;
            id = place;
        }
        for (auto x : g[place]) {
            if (visited[x]) continue;
            visited[x] = 1;
            q.push({x, sz[place] + sum + cnt - sz[x]});
        } 
    }
    return id;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -