Submission #698303

#	Time	Username	Problem	Language	Result	Execution time	Memory
698303		europium	Traffic (IOI10_traffic)	C++17	100 / 100	890 ms	155176 KiB

traffic

#include "traffic.h"
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <iterator>
#include <set>
#include <map>
#include <math.h>
#include <iomanip>
#include <unordered_set>
#include <queue>
#include <climits>
using namespace std;

vector<vector<int>> adj;
vector<int> sub, par;

void dfs(int p, int u){
    par[u] = p;

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

int LocateCentre(int n, int pp[], int s[], int d[]) {
    adj.resize(n);
    sub.resize(n);
    par.resize(n);

    int sum = 0;

    for (int i = 0; i < n; i++){
        sum += pp[i];
        sub[i] = pp[i];
    }

    for (int i = 0; i < n - 1; i++){
        int u = s[i], v = d[i];

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(-1, 0);

    int mx = INT_MAX, ans;

    for (int u = 0; u < n; u++){
        int curr_mx = 0;

        for (auto v : adj[u]){
            if (v == par[u]) curr_mx = max(curr_mx, sum - sub[u]);
            else curr_mx = max(curr_mx, sub[v]);
        }

        if (curr_mx < mx){
            mx = curr_mx;
            ans = u;
        }
    }

    return ans;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:70:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     return ans;
      |            ^~~

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