Submission #837917

#	Time	Username	Problem	Language	Result	Execution time	Memory
837917		thimote75	Traffic (IOI10_traffic)	C++14	100 / 100	847 ms	159104 KiB

traffic

#include "traffic.h"

#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;

idata weight;
idata subtree_weight;
idata parents;

igrid roads;

int dfs (int node, int parent) {
   parents[node] = parent;

   subtree_weight[node] = weight[node];

   for (int next : roads[node]) if (next != parent)
      subtree_weight[node] += dfs(next, node);

   return subtree_weight[node];
}
int count (int source, int target) {
   if (parents[source] == target)
      return subtree_weight[0] - subtree_weight[source];
   return subtree_weight[target];
}
int find (int source) {
   int res = 0;
   for (int u : roads[source])
      res = max(res, count(source, u));
   
   return res;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   weight.resize(N);
   for (int i = 0; i < N; i ++) weight[i] = pp[i];

   roads.resize(N);
   parents.resize(N);
   subtree_weight.resize(N);

   for (int i = 0; i + 1 < N; i ++) {
      roads[S[i]].push_back(D[i]);
      roads[D[i]].push_back(S[i]);
   }

   dfs(0, -1);

   pair<int, int> H = { 2e9 + 10, 0 };

   for (int i = 0; i < N; i ++) {
      pair<int, int> local = { find(i), i };
      H = min(H, local);
   }

   return H.second;
}

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