제출 #745574

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745574		MattTheNub	Traffic (IOI10_traffic)	C++17	100 / 100	883 ms	168344 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

template <class T> using v = vector<T>;
using ll = long long;

ll sum = 0;
v<ll> sums;
v<v<int>> adj;
pair<ll, int> ans = {LLONG_MAX, -1};

void dfs(int node, int par) {
  ll cur = 0;
  for (auto next : adj[node]) {
    if (next != par) {
      dfs(next, node);
      sums[node] += sums[next];
      cur = max(cur, sums[next]);
    }
  }
  cur = max(cur, sum - sums[node]);
  ans = min(ans, {cur, node});
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
  adj.resize(N);
  sums.resize(N);
  for (int i = 0; i < N; i++) {
    sum += pp[i];
    sums[i] = pp[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, -1);
  return ans.second;
}

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