Submission #1241744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241744		julia_08	Traffic (IOI10_traffic)	C++20	50 / 100	37 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] += dp_1[u];
      }
   }

   dp_1[v] += sub[v] - cnt[v];

}

void dfs_2(int v, int p, int n){

   for(auto u : adj[v]){
      if(u != p){
         dp_2[u] = dp_2[v] + dp_1[v] - dp_1[u] + sub[1] - 2 * sub[u];
         dfs_2(u, v, n);
      }
   }

}

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, n);

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

   for(int i=2; i<=n; i++) ans = min(ans, {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