제출 #653788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
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