Submission #362401

#	Time	Username	Problem	Language	Result	Execution time	Memory
362401		Traingle	Traffic (IOI10_traffic)	C++14	100 / 100	1187 ms	141420 KiB

traffic

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

const int MX = 1e6;
const int INF = 2e9 + 1;

int fans;
vector<int> adj[MX], nodes(MX), people(MX), children(MX);

void dfs(int v, int e) {
  for (auto u : adj[v]) {
    if (u == e) {
      continue;
    }
    dfs(u, v);
    children[v] += children[u];
    people[v] = max(people[v], children[u]);
  }
  people[v] = max(people[v], fans - children[v] - nodes[v]);
  children[v] += nodes[v];
}

int LocateCentre(int n, int p[], int d[], int s[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 0; i < n; ++i) {
    fans += p[i];
    nodes[i] = p[i];
  }
  for (int i = 0; i < n - 1; ++i) {
    adj[s[i]].push_back(d[i]);
    adj[d[i]].push_back(s[i]);
  }
  dfs(0, -1);
  int sol = INF, res = -1;
  for (int i = 0; i < n; ++i) {
    if (people[i] < sol) {
      res = i;
      sol = people[i];
    }
  }
  return res;
}

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