Submission #310175

#	Time	Username	Problem	Language	Result	Execution time	Memory
310175		ChungFong	Traffic (IOI10_traffic)	C++11	100 / 100	1260 ms	157048 KiB

traffic

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

using namespace std;
const int MX = 1e6;

int totalFans = 0;

vector<int> roads[MX] ;
int cityFans[MX] ;
int congestionOfCity[MX] ;
int accFans2City[MX];

void dfs (int node, int parent) {

    int maxFansFromARoad ;

    for (auto child: roads[node]) {
        if (child == parent) continue;
        
        dfs(child, node);
        
        maxFansFromARoad = max(maxFansFromARoad , accFans2City[child]);
        
        accFans2City[node] += accFans2City[child];        
    }

    int theOther = totalFans - accFans2City[node] - cityFans[node] ;// the total fans from the other side
    congestionOfCity[node] = max(maxFansFromARoad, theOther);

    accFans2City[node] += cityFans[node];
}

int LocateCentre (int n, int p[], int d[], int s[]) {
    for (int i = 0; i < n; i++) {
        totalFans += p[i];
        cityFans[i] = p[i];
    }

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

    dfs(0, -1);
    
    // find the min-congestion city
    int minIdx = 0 ;
    for (int i=1 ; i<n ; ++i ) {
        if ( congestionOfCity[i] < congestionOfCity[minIdx]) {
            minIdx = i;
        }
    }

    return minIdx;
}

Compilation message (stderr)

traffic.cpp: In function 'void dfs(int, int)':
traffic.cpp:16:9: warning: 'maxFansFromARoad' may be used uninitialized in this function [-Wmaybe-uninitialized]
   16 |     int maxFansFromARoad ;
      |         ^~~~~~~~~~~~~~~~

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