Submission #358579

#	Time	Username	Problem	Language	Result	Execution time	Memory
358579		idk321	Traffic (IOI10_traffic)	C++11	100 / 100	1417 ms	206700 KiB

traffic

#include "traffic.h"

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 1000001;
vector<int> adj[N];
ll sz[N];
ll subSz[N];

void dfs1(int node, int par)
{
    subSz[node] = sz[node];
    for (int next : adj[node])
    {
        if (next == par) continue;
        dfs1(next, node);
        subSz[node] += subSz[next];
    }
}

array<ll, 2> dfs2(int node, int par)
{
    if (par != -1)
    {
        subSz[par] -= subSz[node];
        subSz[node] += subSz[par];
    }

    array<ll, 2> cur = {0, node};
    for (int next : adj[node])
    {
        cur[0] = max(subSz[next], cur[0]);
    }

    for (int next : adj[node])
    {
        if (next == par) continue;
        auto ncur = dfs2(next, node);
        if (ncur < cur) cur = ncur;
    }

    subSz[node] -= subSz[par];
    subSz[par] += subSz[node];

    return cur;
}

int LocateCentre(int n, int p[], int S[], int D[]) {
    for (int i = 0; i < n; i++) sz[i] = p[i];
    for (int i = 0; i < n - 1; i++)
    {
        adj[S[i]].push_back(D[i]);
        adj[D[i]].push_back(S[i]);
    }
    dfs1(0, -1);
    auto res = dfs2(0, -1);
    return res[1];
}

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