Submission #1266268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266268		comgaTramAnh	Traffic (IOI10_traffic)	C++20	100 / 100	598 ms	149120 KiB

traffic

#include <math.h>
#include <vector>
#include "traffic.h"
int sum = 0;
int mini = 2000000007, ans = -1; 
std::vector <int> adj[1000005]; 
int total[1000005];
void dfs(int u, int father) {
  int maxTotal = -1;
  for (int i = 0; i < (int) adj[u].size(); i++) {
    int v = adj[u][i];
    if (v == father) {
      continue; 
    }
    dfs(v, u); 
    maxTotal = std::max(maxTotal, total[v]); 
    total[u] += total[v]; 
  }  
  if (father != -1) {
    maxTotal = std::max(maxTotal, sum - total[u]); 
  }
  if (mini > maxTotal) {
    mini = maxTotal;
    ans = u;
  }
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
  for (int i = 0; i < N - 1; i++) {
    adj[S[i]].push_back(D[i]); 
    adj[D[i]].push_back(S[i]); 
  }  
  for (int i = 0; i < N; i++) {
    total[i] = pp[i]; 
    sum += pp[i]; 
  }
  dfs(0, -1);
  return ans;  
}

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