Submission #1232331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232331		countless	Traffic (IOI10_traffic)	C++20	100 / 100	996 ms	123028 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

int LocateCentre(int N, int pp[], int S[], int D[]) {
    vector<vector<int>> adj(N);
    for (int i = 0; i < N-1; i++) {
        int u = S[i], v = D[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<ll> sum(N);
    auto solve = [&](auto &&solve, int u, int p) -> void {
        sum[u] += pp[u];

        for (auto &v : adj[u]) {
            if (v != p) {
                solve(solve, v, u);
                sum[u] += sum[v];
            }
        }
    };

    solve(solve, 0, 0);

    vector<ll> cand(N);
    auto work = [&](auto &&work, int u, int p) -> void {
        cand[u] = sum[0] - sum[u];
        for (auto &v : adj[u]) {
            if (v != p) {
                cand[u] = max(cand[u], sum[v]);
                work(work, v, u);
            }
        }
    };

    work(work, 0, 0);

    vector<int> o(N);
    iota(o.begin(), o.end(), 0);
    sort(o.begin(), o.end(), [&](int i, int j) {
        if (cand[i] == cand[j]) return i < j;
        return cand[i] < cand[j];
    });

    // for (int i = 0; i < N; i++) {
    //     cerr << i sp cand[i] << endl;
    // }

    return o[0];
}

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