Submission #1249285

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249285		kunzaZa183	Traffic (IOI10_traffic)	C++20	50 / 100	1042 ms	274304 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;
  vector<int> in(N);
  vector<pair<int, int>> vpii;
  vpii.emplace_back(0, 0);

  while (!vpii.empty()) {
  A:
    auto &[cur, par] = vpii.back();

  B:
    if (in[cur] < adj[cur].size()) {
      if (adj[cur][in[cur]] == par) {
        in[cur]++;
        goto B;
      }
      vpii.emplace_back(adj[cur][in[cur]++], cur);
      goto A;
    }

    stree[cur] = pp[cur];
    for (auto a : adj[cur]) {
      if (a != par) {
        stree[cur] += stree[a];
        // cout << cur << " " << a << "\n";
        msi.insert(stree[a]);
      }
    }

    vpii.pop_back();
  }

  // for (auto a : stree)
  //   cout << a << " ";
  // cout << "\n";
  // for (auto a : msi)
  //   cout << a << " ";
  // cout << "\n";

  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