Submission #1007356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007356		phoenix	Traffic (IOI10_traffic)	C++17	100 / 100	635 ms	170836 KiB

traffic

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

const int N = 1000000 + 100;

std::vector<int> g[N];
int sz[N];
int pr[N];

void dfs(int v) {
   for (int to : g[v]) if (to != pr[v]) {
      pr[to] = v;
      dfs(to);
      sz[v] += sz[to];
   }
}

int LocateCentre(int N, int p[], int S[], int D[]) {
   for (int i = 0; i < N; i++)
      sz[i] = p[i];
   for (int i = 0; i < N - 1; i++) {
      g[S[i]].push_back(D[i]);
      g[D[i]].push_back(S[i]);
   }
   dfs(0);
   int ver = 0, mx = 0;
   for (int to : g[ver]) mx = std::max(mx, sz[to]);
   
   for (int i = 1; i < N; i++) {
      int val = 0;
      for (int to : g[i]) if (to != pr[i])
         val = std::max(val, sz[to]);
      val = std::max(val, sz[0] - sz[i]);
      if (val < mx) {
         mx = val;
         ver = i;
      }
   }
   return ver;
}

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