Submission #1241764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241764		julia_08	Traffic (IOI10_traffic)	C++20	50 / 100	38 ms	17988 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAXN = 1e5 + 10;

ll cnt[MAXN], sub[MAXN];

ll dp_1[MAXN], dp_2[MAXN];

vector<int> adj[MAXN];

void dfs_1(int v, int p){

   dp_1[v] = 0;

   sub[v] = cnt[v];

   for(auto u : adj[v]){
      if(u != p){
         dfs_1(u, v);
         sub[v] += sub[u];
         dp_1[v] = max({dp_1[v], dp_1[u], sub[u]});
      }
   }

}

void dfs_2(int v, int p){

   ll cur_max = 0;

   for(auto u : adj[v]){
      if(u != p){
         dp_2[u] = max({dp_2[v], sub[1] - sub[u], cur_max});
         cur_max = max({cur_max, dp_1[u], sub[u]});
      }
   }

   reverse(adj[v].begin(), adj[v].end());

   cur_max = 0;

   for(auto u : adj[v]){
      if(u != p){
         dp_2[u] = max(dp_2[u], cur_max);
         cur_max = max({cur_max, dp_1[u], sub[u]});
      }
   }

   for(auto u : adj[v]) if(u != p) dfs_2(u, v);

}

int LocateCentre(int n, int p[], int s[], int d[]){

   for(int i=1; i<=n; i++) adj[i].clear();

   for(int i=0; i<n; i++) cnt[i + 1] = p[i];

   for(int i=0; i<(n - 1); i++){
      adj[s[i] + 1].push_back(d[i] + 1);
      adj[d[i] + 1].push_back(s[i] + 1);
   }

   dfs_1(1, 1);

   dp_2[1] = 0;

   dfs_2(1, 1);

   pair<ll, int> ans = {dp_1[1], 1};

   for(int i=2; i<=n; i++) ans = min(ans, {max(dp_1[i], dp_2[i]), i});

   return ans.second - 1;

}

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