Submission #519536

#	Time	Username	Problem	Language	Result	Execution time	Memory
519536		megargayu	Traffic (IOI10_traffic)	C++17	100 / 100	988 ms	143272 KiB

traffic

// https://oj.uz/problem/view/IOI10_traffic
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MAX_N 1000000
#define INF 2e9

vector<ll> sum(MAX_N);
vector<int> parent(MAX_N);
vector<vector<int>> adj(MAX_N);
ll maxSum = 0;

void dfs(int par, int cur)
{
  for (const int &w : adj[cur])
    if (w != par)
    {
      parent[w] = cur;
      dfs(cur, w);
      sum[cur] += sum[w];
    }
}

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

  for (int i = 0; i < N - 1; ++i)
  {
    adj[S[i]].push_back(D[i]);
    adj[D[i]].push_back(S[i]);
  }

  dfs(0, 0);

  ll minOut = INF, minI = INF;
  for (int i = 0; i < N; ++i)
  {
    ll maxOut = maxSum - sum[i];
    for (const int &w : adj[i])
      if (w != parent[i]) // don't check parent -> child relationship, because 
        maxOut = max(maxOut, sum[w]); // that is calculated differently

    if (maxOut < minOut)
    {
      minOut = maxOut;
      minI = i;
    }
  }
  
  return minI;
}

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