Submission #550152

#	Time	Username	Problem	Language	Result	Execution time	Memory
550152		Mahmudul_Kabir	Traffic (IOI10_traffic)	C++14	0 / 100	19 ms	39372 KiB

traffic

#include "traffic.h"
#include "bits/stdc++.h"
 
#define sp <<" "
#define el <<"\n"
#define S second
#define F first
#define pb push_back
#define all(ar) ar.begin(),ar.end() 
#define pii pair<ll,ll> 
 
 
using namespace std;
using ll = long long;
using ld = long double;

const ll mod = 1000000007;
const ll oo = 3372036000000000;
const ll si = 1000005;

vector<int> g[1000001]; 
int *pep; 
ll mn[1000001], val[1000001]; 

void dfs(int v,int p = -1){
   val[v] += pep[v]; 
   for(int r: g[v]){
      if(r == p) continue; 
      dfs(r,v); 
      val[v] += val[r]; 
   }
   return; 
}

void reroot(int v,int p = -1){
   for(int r: g[v]) mn[v] = max(mn[v], val[r]);
   for(int r: g[v]){
      if(r == p) continue; 
      val[v] -= val[r]; 
      dfs(r,v);
      val[v] += val[r]; 
   }
   return; 
}

int LocateCentre(int N, int pp[], int S[], int D[]){
   pep = pp;
   for(int i = 0; i < N - 1; i++){
      g[S[i]].pb(D[i]);
      g[D[i]].pb(S[i]); 
   }
   memset(mn,-1,sizeof(mn)); 
   memset(val,0,sizeof(val)); 
   dfs(0); 
   reroot(0); 
   pii ans = {1152921504606846976,-1}; 
   for(int i = 0; i < N; i++) ans = min(ans,{mn[i],i}); 
   return ans.S; 
}

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