Submission #310177

#	Time	Username	Problem	Language	Result	Execution time	Memory
310177		shihs	Traffic (IOI10_traffic)	C++11	100 / 100	1300 ms	141284 KiB

traffic

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

using namespace std;
const int MX = 1e6;

int totalFans = 0;

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

void dfs (int node, int parent) {

    for (auto x: roads[node]) {
        if (x == parent) continue;
        dfs(x, node);
        accFans2City[node] += accFans2City[x];
        congestionOfCity[node] = max(congestionOfCity[node], accFans2City[x]);
    }
    
    congestionOfCity[node] = max(congestionOfCity[node], totalFans - accFans2City[node] - cityFans[node]);

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

    int minIdx = 0;

    for (int i = 1; i < n; ++i) {
        if (congestionOfCity[i]<congestionOfCity[minIdx]) {
            minIdx = i;
        }
    }

    return minIdx;
}

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