Submission #411809

#	Time	Username	Problem	Language	Result	Execution time	Memory
411809		zwliew	Traffic (IOI10_traffic)	C++17	100 / 100	1259 ms	154956 KiB

traffic

#include "traffic.h"
#include <algorithm>
#include <iostream>
#include <vector>
#include <array>

using namespace std;

vector<vector<int> > adj;
vector<int> dp;
array<int, 2> ans;
vector<int> cnt;
void dfs(int u, int p) {
   dp[u] = cnt[u];
   for (int v : adj[u]) {
      if (v != p) {
         dfs(v, u);
         dp[u] += dp[v];
      }
   }
}

void dfs2(int u, int p) {
   int cur = 0;
   for (int v : adj[u]) {
      cur = max(cur, dp[v]);
   }
   if (cur < ans[1]) {
      ans = {u, cur};
   }
   for (int v : adj[u]) {
      if (v == p) continue;
      dp[u] -= dp[v];
      dp[v] += dp[u];
      dfs2(v, u);
      dp[v] -= dp[u];
      dp[u] += dp[v];
   }
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   cnt.resize(N);
   for (int i = 0; i < N; ++i) {
      cnt[i] = pp[i];
   }
   dp.resize(N);
   adj.resize(N);
   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);
   ans = {0, 0};
   for (int v : adj[0]) {
      ans[1] = max(ans[1], dp[v]);
   }

   dfs2(0, -1);
   return ans[0];
}

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