Submission #1249286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249286		kunzaZa183	Traffic (IOI10_traffic)	C++20	100 / 100	3486 ms	231328 KiB

traffic

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

vector<vector<int>> adj;
const int mn = 1e6;
ll stree[mn] = {};
multiset<ll> msi;

int *pp2;
ll tot;

ll mini;
int ans;

void dfs(int cur, int par) {
  stree[cur] = pp2[cur];
  for (auto a : adj[cur])
    if (a != par) {
      dfs(a, cur);
      stree[cur] += stree[a];
      msi.insert(stree[a]);
    }
};

void 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])));
    }
  }
};

int LocateCentre(int N, int pp[], int S[], int D[]) {
  if (N == 1)
    return 0;
  adj.resize(N);
  pp2 = pp;
  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);

  tot = accumulate(pp, pp + N, 0ll);
  mini = *msi.rbegin();
  ans = 0;

  fvvi2(0, 0);

  return ans;
}

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