Submission #956425

#	Time	Username	Problem	Language	Result	Execution time	Memory
956425		emad234	Traffic (IOI10_traffic)	C++17	100 / 100	999 ms	178716 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll mxN = 1e6 + 5;
using namespace std;
vector<vector<int>>v;
int dpD[mxN],dpU[mxN], ans[mxN];
int val[mxN];
void dfs(int u,int par){
   dpD[u] = val[u];
   for(auto x : v[u]){
      if(x == par) continue;
      dfs(x,u);
      ans[u] = max(ans[u],dpD[x]);
      dpD[u] += dpD[x];
   }
}
void hfs(int u,int par){
   if(par != -1){
      dpU[u] = dpU[par] + dpD[par] - dpD[u];
      ans[u] = max(ans[u],dpU[u]);
   }
   for(auto x : v[u]){
      if(x == par) continue;
      hfs(x,u);
   }
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
   v.resize(N + 3);
   for(int i = 0;i < N;i++){
      val[i] = pp[i];
      if(i == N - 1) continue;
      v[S[i]].push_back(D[i]);
      v[D[i]].push_back(S[i]);
   }
   int mn = INT_MAX,mxid = -1;
   dfs(0,-1);
   hfs(0,-1);
   for (int i = 0; i < N; i++)
   {
      if(ans[i] < mn){
         mn = ans[i];
         mxid = i;
      }
   }
   return mxid;
}

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