Submission #549348

#	Time	Username	Problem	Language	Result	Execution time	Memory
549348		palilo	Traffic (IOI10_traffic)	C++17	0 / 100	1 ms	568 KiB

traffic

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

int LocateCentre(int n, int p[], int s[], int d[]) {
    using namespace std;
    vector<vector<int>> adj(n);
    for (int i = 0; i < n; ++i) {
        adj[s[i]].emplace_back(d[i]);
        adj[d[i]].emplace_back(s[i]);
    }
    auto dfs_rev_order = [&](int root) {
        vector<int> stk = {root}, ord(n);
        for (auto& u : ord) {
            u = stk.back();
            stk.pop_back();
            for (const auto& v : adj[u]) {
                adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
                stk.emplace_back(v);
            }
        }
        reverse(ord.begin(), ord.end());
        return ord;
    }(0);
    const auto total = accumulate(p, p + n, 0);
    vector<int> subtree_size(n);
    vector<int64_t> dp(n);
    for (const auto& u : dfs_rev_order) {
        for (const auto& v : adj[u]) {
            subtree_size[u] += subtree_size[v];
            dp[u] += subtree_size[v];
        }
    }
    int u = 0;
    for (bool update = true; update;) {
        update = false;
        for (const auto& v : adj[u]) {
            if (dp[u] > dp[v] + (total - subtree_size[v])) {
                u = v;
                update = true;
            }
        }
    }
    return u;
}

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