Submission #1288247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288247		Faisal_Saqib	Traffic (IOI10_traffic)	C++20	100 / 100	566 ms	149252 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int dp[N];
vector<int> ma[N];
void dfs(int x,int p=-1)
{
   for(auto y:ma[x])
   {
      if(y!=p)
      {
         dfs(y,x);
         dp[x]+=dp[y];
      }
   }
}
pair<int,int> bst={2e9,2e9};
void dfs_(int x,int p=-1)
{
   int mx=0;
   for(auto y:ma[x])mx=max(mx,dp[y]);
   bst=min(bst,make_pair(mx,x));
   for(auto y:ma[x])
   {
      if(y!=p)
      {
         dp[x]-=dp[y];
         dp[y]+=dp[x];
         dfs_(y,x);
         dp[y]-=dp[x];
         dp[x]+=dp[y];
      }
   }
}
int LocateCentre(int n, int pp[], int S[], int D[]) {
   for(int i=0;i<n-1;i++)
   {
      ma[S[i]].push_back(D[i]);
      ma[D[i]].push_back(S[i]);
   }
   for(int i=0;i<n;i++)
   {
      dp[i]=pp[i];
   }
   dfs(0);
   bst=make_pair(2e9,2e9);
   dfs_(0);
   return bst.second;
}

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