Submission #1312628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312628		niwrad	Traffic (IOI10_traffic)	C++20	100 / 100	545 ms	152904 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

using namespace std;
vector<vector<int>> graph;
vector<int> sz;
int total = 0;
vector<int> vec;
int dfs(int node, int prev) {
   int mx = 0;
   int sum = vec[node];
   for (auto next : graph[node]) {
      if (next != prev) {
         int val = dfs(next, node);
         mx = max(mx, val);
         sum += val;
      }
   }
   mx = max(total - sum, mx);
   sz[node] = mx;
   return sum;
}



int LocateCentre(int N, int pp[], int S[], int D[]) {
   graph.resize(N);
   sz.resize(N);
   vec.resize(N);
   for (int i = 0; i < N; i++) {
      vec[i] = pp[i];
      total += pp[i];
   }
   for (int i = 0; i < N - 1; i++) {
      graph[S[i]].push_back(D[i]);
      graph[D[i]].push_back(S[i]);
   }
   dfs(0, -1);
   int ans = -1;
   int num = 2e9 + 2;
   for (int i = 0; i < N; i++) {
      if (sz[i] < num) {
         num = sz[i];
         ans = i;
      }
   }
   return ans;
}

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