Submission #653788

#	Time	Username	Problem	Language	Result	Execution time	Memory
653788		alvinpiter	Traffic (IOI10_traffic)	C++17	0 / 100	18 ms	23940 KiB

traffic

/*
1. Root the tree at node 1.
2. Run DFS to calculate the number of people living in each subtree.
3. Run another DFS to decide the best city for the arena. If we treat the current city as the
   arena, then the most congested road will be one of the edges incident to it.
*/

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

vector<int> adj[MAXN + 3];
int P[MAXN + 3], sz[MAXN + 3], bestTraffic, bestCity;

void dfs1(int u, int prev) {
   sz[u] = P[u];
   for (auto v: adj[u]) {
      if (v != prev) {
         dfs1(v, u);
         sz[u] += sz[v];
      }
   }
}

void dfs2(int u, int prev) {
   int maxTraffic = sz[1] - sz[u]; // From u to its parent
   for (auto v: adj[u]) {
      if (v != prev) {
         maxTraffic = max(maxTraffic, sz[v]);
      }
   }

   if (maxTraffic < bestTraffic) {
      bestTraffic = maxTraffic;
      bestCity = u;
   }

   for (auto v: adj[u]) {
      if (v != prev) {
         dfs2(v, u);
      }
   }
}

int LocateCentre(int N, int p[], int S[], int D[]) {
   for (int i = 0; i < N; i++) P[i] = p[i];
   for (int i = 0; i < N - 1; i++) {
      adj[S[i]].push_back(D[i]);
      adj[D[i]].push_back(S[i]);
   }

   dfs1(1, -1);

   bestTraffic = 2000000001;
   bestCity = -1;

   dfs2(1, -1);

   return bestCity;
}

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