Submission #501505

#	Time	Username	Problem	Language	Result	Execution time	Memory
501505		aryan12	Traffic (IOI10_traffic)	C++17	100 / 100	982 ms	168516 KiB

traffic

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

const long long MAXN = 1e6 + 5;
vector<long long> g[MAXN];
long long subtree[MAXN], sum = 0;
long long max_val = 1e15, ans = 0;
long long value[MAXN];

void dfs(long long node, long long par) {
   subtree[node] += value[node];
   long long cur_ans = 0, cur_sum = 0;
   for(long long i = 0; i < g[node].size(); i++) {
      if(g[node][i] == par) continue;
      dfs(g[node][i], node);
      subtree[node] += subtree[g[node][i]];
      cur_ans = max(cur_ans, subtree[g[node][i]]);
      cur_sum += subtree[g[node][i]];
   }
   cur_ans = max(cur_ans, sum - cur_sum - value[node]);
   if(max_val > cur_ans) {
      max_val = cur_ans;
      ans = node;
   }
}

int LocateCentre(int N, int values[], int U[], int V[]) {
   for(long long i = 0; i < N - 1; i++) {
      g[U[i]].push_back(V[i]);
      g[V[i]].push_back(U[i]);
   }
   for(long long i = 0; i < N; i++) {
      sum += values[i];
      value[i] = values[i];
   }
   dfs(0, -1);
   return ans;
}

Compilation message (stderr)

traffic.cpp: In function 'void dfs(long long int, long long int)':
traffic.cpp:14:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |    for(long long i = 0; i < g[node].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~

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