Submission #758703

#	Time	Username	Problem	Language	Result	Execution time	Memory
758703		JANCARAPAN	Traffic (IOI10_traffic)	C++17	100 / 100	933 ms	178472 KiB

traffic

#include <bits/stdc++.h>
using namespace std;  
#define ll long long
#define fi first
#define se second
#define sz(a) (long long) a.size()
#define endl '\n'

const long long INF = 1e18, MOD = 1e9+7; 

int LocateCentre(int n, int* P, int* S, int *D) {
  int tot = 0;
  for (int i = 0; i < n; i++) {
    tot += P[i];
  }
  vector g(n, vector<int>());
  for (int i = 0; i < n - 1; i++) {
    g[S[i]].push_back(D[i]);
    g[D[i]].push_back(S[i]);
  }
  int mn = 2e9+5, who = -1;
  
  function<int(int, int)> Dfs = [&](int v, int par) {
    int down = 0, mx = 0;
    for (auto u : g[v]) {
      if (u == par) continue;
      int x = Dfs(u, v);
      mx = max(mx, x);
      down += x;
    }
    down += P[v];
    mx = max(mx, tot - down);
    if (mx < mn) {
      mn = mx;
      who = v;
    }
    return down;
  };
  Dfs(0, -1);
  return who;
}

//signed main() {
  //ios_base::sync_with_stdio(false);
  //cin.tie(0);
  //int tt = 1;
  //cin >> tt;
  //while (tt--) {
    //test_case();
  //}
  //return 0;
//}

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