제출 #430619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
430619		four_specks	Traffic (IOI10_traffic)	C++17	100 / 100	1332 ms	170736 KiB

traffic

#include "traffic.h"

#include <bits/stdc++.h>

using namespace std;

vector<int> adj[1000000];

int par[1000000];
int acc[1000000];

int p_sum;

int dfs(int N, int P[], int u, int p)
{
    par[u] = p;

    acc[u] = P[u];
    for (const int &v : adj[u])
    {
        if (v != p)
            acc[u] += dfs(N, P, v, u);
    }

    return acc[u];
}

int LocateCentre(int N, int P[], int S[], int D[])
{
    p_sum = 0;
    for (int i = 0; i < N; i++)
        p_sum += P[i];

    for (int j = 0; j < N - 1; j++)
        adj[S[j]].push_back(D[j]),
        adj[D[j]].push_back(S[j]);

    int s = -1;
    for (int i = 0; i < N; i++)
    {
        if (adj[i].size() == 1)
        {
            s = i;
            break;
        }
    }

    dfs(N, P, s, -1);

    int city = -1;

    int min_traffic = INT_MAX;
    for (int i = 0; i < N; i++)
    {
        int traffic = 0;
        for (const int &v : adj[i])
        {
            if (v == par[i])
                traffic = max(traffic, p_sum - acc[i]);
            else
                traffic = max(traffic, acc[v]);
        }

        if (traffic < min_traffic)
        {
            city = i;
            min_traffic = traffic;
        }
    }

    return city;
}

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