Submission #1228087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228087		Hamed_Ghaffari	Traffic (IOI10_traffic)	C++20	100 / 100	568 ms	149136 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

const int MXN = 1e6+5;

int ans=2e9, tot, sz[MXN], ver=0;
vector<int> g[MXN];

void dfs(int v, int p=-1) {
   int mx = 0;
   for(int u : g[v])
      if(u!=p) {
         dfs(u, v);
         sz[v] += sz[u];
         mx = max(mx, sz[u]);
      }
   if(p!=-1) mx = max(mx, tot-sz[v]);
   if(mx<ans) {
      ans = mx;
      ver = v;
   }
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   for(int i=0; i<N-1; i++) g[S[i]].push_back(D[i]), g[D[i]].push_back(S[i]);
   for(int i=0; i<N; i++) tot += pp[i], sz[i] = pp[i];
   dfs(0);
   return ver;
}

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