Submission #1194358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194358		SonicML	Traffic (IOI10_traffic)	C++17	100 / 100	891 ms	157020 KiB

traffic

#include <vector>
#include "traffic.h"

using namespace std;

int const INF = 2e9+1;

int const NMAX = 1e6;
int val[1 + NMAX];
int ans[1 + NMAX];
vector <int> g[1 + NMAX];

int total;
int sub[1 + NMAX];

void DFS(int node, int parent) {
 
  ans[node] = 0;	
  sub[node] = val[node];
  for(int i = 0;i < g[node].size();i++) {
    int to = g[node][i]; 
    if(to != parent) {
      DFS(to, node);
      ans[node] = max(ans[node], sub[to]);
      sub[node] += sub[to];
    }
  }
  ans[node] = max(ans[node], total - sub[node]);
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
  int n;
  n = N;
  for(int i = 1;i <= n;i++) {
    val[i] = pp[i-1];
    total += val[i];
  }
  for(int i = 1;i < n;i++) {
    int a, b;
    a = S[i-1] + 1; 
    b = D[i-1] + 1;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  DFS(1, 1);
  int sol = INF, best = 0;
  for(int i = 1;i <= n;i++) {
    if(ans[i] < sol) {
      best = i;
      sol = ans[i];
    }
  }
  return (best-1);
}	

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