제출 #586415

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586415		blue	Traffic (IOI10_traffic)	C++17	100 / 100	938 ms	170696 KiB

traffic

#include "traffic.h"
#include <vector>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;

const int mx = 1'000'000;
const ll inf = 1'000'000'000'000'000'000LL;

int N;
vll pop(mx);
ll tot = 0;
vi edge[mx];

int res = -1;
ll cost = inf;

void dfs(int u, int p)
{
   ll curr = 0;

   for(int v : edge[u])
   {
      if(v == p)
         continue;

      dfs(v, u);
      pop[u] += pop[v];
      curr = max(curr, pop[v]);
   }

   curr = max(curr, tot - pop[u]);

   if(curr < cost)
   {
      res = u;
      cost = curr;
   }
}

int LocateCentre(int N_, int pp[], int S[], int D[]) 
{
   N = N_;

   for(int i = 0; i < N; i++)
   {
      pop[i] = pp[i];
      tot += pop[i];
   }

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

   dfs(0, -1);

   return res;
}

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