Submission #583530

#	Time	Username	Problem	Language	Result	Execution time	Memory
583530		vilji	Traffic (IOI10_traffic)	C++17	100 / 100	1127 ms	174384 KiB

traffic

#include <bits/stdc++.h>

#define rep(i, a, b) for (int i = (a); i < (b); i++)

#include "traffic.h"

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;

#define INF 1'000'000'050

#define pb push_back

int n;
int W[1'000'050];
vi E[1'000'050];

int sz[1'000'050];

int num = 0;


int dfs(int at, int p) {
  if (sz[at] != -1) return sz[at];
  int tot = W[at];
  // cout << "ello " << at << " " << p << endl;
  for (auto e : E[at]) {
    // cout << "ello" << endl;
    if (e != p) tot += dfs(e, at);
  }
  return sz[at] = tot;
}

ii dfs2(int at, int p) {
  int m = 0;
  int tot = 0;
  ii bst = {INF, -1};
  for (auto e : E[at]) {
    if (e != p) {
      m = max(m, sz[e]);
      tot += sz[e];
      bst = min(bst, dfs2(e, at));
    }
  }
  m = max(m, num - W[at] - tot);
  bst = min(bst, {m, at});
  return bst;
}

int LocateCentre(int N, int P[], int S[], int D[]) {
  memset(sz, -1, sizeof(sz));
  // cout << "----" << endl;
  n = N;
  rep(i, 0, n) { num += W[i] = P[i]; }

  rep(i, 0, n - 1) {
    E[S[i]].pb(D[i]);
    E[D[i]].pb(S[i]);
  }

  dfs(0, -1);
  // rep(i, 0, n) cout << sz[i] << endl;
  int ans = dfs2(0, -1).second;
  // cout << "---" << endl;
  return ans;
}

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