제출 #1182658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182658		hamzabc	Traffic (IOI10_traffic)	C++20	100 / 100	468 ms	133552 KiB

traffic

#ifndef LOCAL
#include "traffic.h"
#endif
#include <iostream>
#include <vector>


using namespace std;


vector<vector<int>> graph;
vector<int> tmp;


void dfs1(int n, int p){
   for (auto go : graph[n]){
      if (go == p)
         continue;
      dfs1(go, n);
      tmp[n] += tmp[go];
   }
}


pair<long long int, int> dfs2(int n, int p, long long int p2=0){
   long long int mx = 0;
   int j = -1;
   for (auto go : graph[n]){
      if (go == p)
         continue;
      if (tmp[go] > mx){
         mx = tmp[go];
         j = go;
      }
   }
   if (p2 >= mx){
      return { p2, n };
   }else{
      auto u = dfs2(j, n, p2 + tmp[n] - tmp[j]);
      if (u.first >= mx){
         return { mx, n };
      }else{
         return u;
      }
   }
}


int LocateCentre(int N, int pp[], int S[], int D[]) {
   graph.resize(N);
   tmp.resize(N);
   for (int i = 0; i < N - 1; i++){
      graph[S[i]].push_back(D[i]);
      graph[D[i]].push_back(S[i]);
   }
   for (int i = 0; i < N; i++)
      tmp[i] += pp[i];
   dfs1(0, 0);
   return dfs2(0, 0, 0).second;
}

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