Submission #467447

#	Time	Username	Problem	Language	Result	Execution time	Memory
467447		trxke01	Traffic (IOI10_traffic)	C++17	100 / 100	1323 ms	166816 KiB

traffic

//HEADER
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair<int, int> pii;

vector<vector<int>> adj(1e6+5);
// congestion passing through each city
vector<int> cong(1e6+5);
int minCongestion;
int bestCity;

int dfs1(int curr, int prev, const int P[]){
    int congestion = P[curr];
    for(int next : adj[curr]){
        if(next != prev){
            congestion += dfs1(next, curr, P);
        }
    }
    cong[curr] = congestion;
    return congestion;
}

void dfs2(int curr, int prev, const int P[]){
    // test
    int mostCong = 0;
    for(int next : adj[curr]){
        mostCong = max(mostCong, cong[next]);
    }
    // cout << "most for " << curr << " is " << mostCong << "\n";
    if(mostCong < minCongestion){
        minCongestion = mostCong;
        bestCity = curr;
    }
    for(int next : adj[curr]){
        if(next != prev){
            // reroot
            cong[curr] -= cong[next];
            cong[next] += cong[curr];

            // go
            dfs2(next, curr, P);
            // roll back
            cong[next] -= cong[curr];
            cong[curr] += cong[next];
        }
    }
}

int LocateCentre(int N, int P[], int S[], int D[]){
    for(int i = 0; i < N-1; i++){
        int u = S[i];
        int v = D[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // start at 0
    bestCity = 0;
    minCongestion = 2e9+1e8;

    // initialize cong with dfs1
    dfs1(0, -1, P);

    // // test
    // for(int i = 0; i < N; i++){
    //     cout << i << " : " << cong[i] << "\n";
    // }

    // reroot with dfs2
    dfs2(0, -1, P);

    // return
    return bestCity;
}

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