Submission #1249278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249278		kunzaZa183	Traffic (IOI10_traffic)	C++20	50 / 100	1032 ms	262404 KiB

traffic

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

int LocateCentre(int N, int pp[], int S[], int D[]) {
  if (N == 1)
    return 0;
  vector<vector<int>> adj(N);
  for (int i = 0; i < N - 1; i++) {
    adj[S[i]].push_back(D[i]), adj[D[i]].push_back(S[i]);
  }

  vector<ll> stree(N);
  multiset<ll> msi;
  function<void(int, int)> dfs = [&](int cur, int par) {
    stree[cur] = pp[cur];
    for (auto a : adj[cur])
      if (a != par) {
        dfs(a, cur);
        stree[cur] += stree[a];
        msi.insert(stree[a]);
      }
  };
  dfs(0, 0);

  ll tot = accumulate(pp, pp + N, 0ll);
  ll mini = *msi.rbegin();
  int ans = 0;
  function<void(int, int)> fvvi2 = [&](int cur, int par) {
    if (*msi.rbegin() < mini) {
      ans = cur;
      mini = *msi.rbegin();
    }
    for (auto a : adj[cur]) {
      if (a != par) {
        msi.erase(msi.find(stree[a]));
        msi.insert(tot - stree[a]);
        fvvi2(a, cur);
        msi.insert(stree[a]);
        msi.erase(msi.find((tot - stree[a])));
      }
    }
  };
  fvvi2(0, 0);

  return ans;
}

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