Submission #411422

#	Time	Username	Problem	Language	Result	Execution time	Memory
411422		alextodoran	Traffic (IOI10_traffic)	C++17	100 / 100	1274 ms	172176 KiB

traffic

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;

typedef long long ll;

const int N_MAX = 1000000;

int n;

int p[N_MAX];

int subSize[N_MAX];

vector <int> edges[N_MAX];
int parent[N_MAX];

void dfs (int u)
{
    subSize[u] = p[u];
    for(int v : edges[u])
        if(v != parent[u])
        {
            parent[v] = u;
            dfs(v);
            subSize[u] += subSize[v];
        }
}

int LocateCentre (int N, int P[], int X[], int Y[])
{
    n = N;
    for(int u = 0; u < n; u++)
        p[u] = P[u];
    for(int i = 0; i < n - 1; i++)
    {
        edges[X[i]].push_back(Y[i]);
        edges[Y[i]].push_back(X[i]);
    }
    parent[0] = -1;
    dfs(0);
    int best = INT_MAX;
    int answer = -1;
    for(int u = 0; u < n; u++)
    {
        int maxFlow = subSize[0] - subSize[u];
        for(int v : edges[u])
            if(v != parent[u])
                maxFlow = max(maxFlow, subSize[v]);
        if(maxFlow < best)
        {
            best = maxFlow;
            answer = u;
        }
    }
    for(int i = 0; i < n; i++)
        edges[i].clear();
    return answer;
}

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