Submission #1214672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214672		12baater	Traffic (IOI10_traffic)	C++20	100 / 100	588 ms	145196 KiB

traffic

#include "traffic.h"
#include <iostream>
#include <vector>
using namespace std;

vector<int> ADJ[1000010];
int maxSubtree[1000010];
int subtreeSize[1000010];
int notSubtree[1000010];
int p[1000010];

void dfs(int node, int parent) {
   for (int i = 0; i < ADJ[node].size(); i++) {
      if(ADJ[node][i] == parent) continue;
      dfs(ADJ[node][i], node);
   }
   if(node == 0) return;
   subtreeSize[parent] += subtreeSize[node] + p[node];
   maxSubtree[parent] = max(maxSubtree[parent], subtreeSize[node] + p[node]);
   notSubtree[parent] -= subtreeSize[node] + p[node];
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   int total = 0;
   for(int i = 0; i < N; i++) {
      p[i] = pp[i];
      total += pp[i];
      ADJ[D[i]].push_back(S[i]);
      ADJ[S[i]].push_back(D[i]);
   }
   for(int i = 0; i < N; i++) {
      notSubtree[i] = total-pp[i];
   }
   dfs(0,0);
   int bestNode = 0;
   int bestMax = 2000000000;

   for(int i = 0; i < N; i++) {
      if (max(maxSubtree[i],notSubtree[i]) < bestMax) {
         bestMax = max(maxSubtree[i],notSubtree[i]);
         bestNode = i;
      }
   }
   return bestNode;
}

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