Submission #1212329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212329		adriines06	Traffic (IOI10_traffic)	C++20	100 / 100	716 ms	157044 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>adj;
vector<int>p,maxi,st;
int t=0;
void dfs(int u,int parent){
   st[u]+=p[u];
   for(int v: adj[u]){
      if(v!=parent){
         dfs(v,u);
         st[u]+=st[v];
         maxi[u]=max(maxi[u],st[v]);
      }
   }
   maxi[u]=max(maxi[u],t-st[u]);
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
   adj.resize(N);
   for(int i=0;i<N-1;i++){
      int a=S[i]; int b= D[i];
      adj[a].push_back(b);
      adj[b].push_back(a);
   }
   p.resize(N);
   maxi.assign(N,0);
   st.assign(N,0);
   for(int i=0;i<N;i++){
      p[i]=pp[i];
      t+=p[i];
   }
   dfs(0,-1);
   
   int mini=2e9+5,ans;
   for(int i=0;i<N;i++){
      if(mini>maxi[i]){
         mini=maxi[i];
         ans=i;
      }
   }
   return ans;
}

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