Submission #393866

#	Time	Username	Problem	Language	Result	Execution time	Memory
393866		fahimcp495	Traffic (IOI10_traffic)	C++17	100 / 100	1411 ms	175268 KiB

traffic

#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;

void dfs(int u, int p, int val[], vector<vector<int>>& t, vector<int>& sub_val, vector<int>& mx) {
  sub_val[u] = val[u];
  for (int& v: t[u]) {
    if(v != p) {
      dfs(v, u, val, t, sub_val, mx);
      mx[u] = max(mx[u], sub_val[v]);
      sub_val[u] += sub_val[v];
    }
  }
}

int LocateCentre(int n, int p[], int s[], int d[]) {
  vector<vector<int>> t(n);
  for (int i = 0; i < n-1; ++i){
    t[s[i]].push_back(d[i]);
    t[d[i]].push_back(s[i]);
  }
  vector<int> sub_val(n), mx(n);
  dfs(0, -1, p, t, sub_val, mx);
  int mn = mx[0];
  int tot = accumulate(p, p+n, 0);
  for (int u = 1; u < n; ++u){
    mx[u] = max(mx[u], tot-(sub_val[u]));
    mn = min(mn, mx[u]);
  }
  for (int u = 0; u < n; ++u){
    if(mx[u]==mn) return u;
  }
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:17:26: warning: control reaches end of non-void function [-Wreturn-type]
   17 |   vector<vector<int>> t(n);
      |                          ^

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