제출 #1023695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1023695		HappyCapybara	Traffic (IOI10_traffic)	C++17	100 / 100	668 ms	139696 KiB

traffic

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

vector<bool> seen;
vector<int> p, PP;
vector<vector<int>> g;

int dfs(int cur){
   if (seen[cur]) return 0;
   seen[cur] = true;
   p[cur] += PP[cur];
   for (int next : g[cur]) p[cur] += dfs(next);
   return p[cur];
}

int LocateCentre(int N, int pp[], int S[], int D[]){
   int t = 0;
   PP.resize(N);
   for (int i=0; i<N; i++){
      PP[i] = pp[i];
      t += PP[i];
   }
   g.resize(N);
   for (int i=0; i<N; i++){
      g[S[i]].push_back(D[i]);
      g[D[i]].push_back(S[i]);
   }
   seen.resize(N, false);
   p.resize(N, 0);
   dfs(0);
   int bsf = t, best = -1;
   for (int i=0; i<N; i++){
      int worst = t-p[i];
      for (int j : g[i]){
         if (p[j] < p[i]) worst = max(worst, p[j]);
      }
      if (worst < bsf){
         bsf = worst;
         best = i;
      }
   }
   return best;
}

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