Submission #339148

#	Time	Username	Problem	Language	Result	Execution time	Memory
339148		Victor	Traffic (IOI10_traffic)	C++17	100 / 100	1129 ms	169836 KiB

traffic

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define INF 1000000000
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;

vi graph[1000005];
vii traffic;
int subs[1000005], pop[1000005], best = 2 * INF + 1, ans;
bitset<1000005> vis;

void getsubs(int u)
{
    vis[u] = 1;
    int s = 0;
    trav(v, graph[u])
    {
        if (vis[v])
            continue;
        getsubs(v);
        s += subs[v] + pop[v];
    }
    subs[u] = s;
}

void solve(int u, int over)
{
    vis[u] = 1;
    traffic.clear();

    if (!graph[u].size() || (graph[u].size() == 1 && vis[graph[u][0]]))
    {
        if (over < best)
            best = over, ans = u;
        return;
    }

    trav(v, graph[u])
    {
        if (vis[v])
            continue;
        traffic.emplace_back(subs[v] + pop[v], v);
    }

    sort(traffic.begin(), traffic.end(), greater<>());
    if (max(traffic[0].first, over) < best)
    {
        best = max(traffic[0].first, over);
        ans = u;
    }

    over += pop[u];
    rep(i, 1, (int)traffic.size())
        over += traffic[i].first;

    solve(traffic[0].second, over);
}

int LocateCentre(int n, int p[], int s[], int d[])
{
    fill(graph, graph + 1000000, vi());
    rep(i, 0, n) pop[i] = p[i];
    rep(i, 0, n - 1)
    {
        graph[s[i]].push_back(d[i]);
        graph[d[i]].push_back(s[i]);
    }

    vis.reset();
    getsubs(0);
    vis.reset();
    solve(0, 0);
    return ans;
}

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