Submission #764276

#	Time	Username	Problem	Language	Result	Execution time	Memory
764276		Blagoj	Traffic (IOI10_traffic)	C++17	50 / 100	371 ms	126528 KiB

traffic

#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 = q.front().second;
        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, pp[place] + sum + cnt - sz[x]});
        } 
    }
    return id;
}

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