Submission #466104

#	Time	Username	Problem	Language	Result	Execution time	Memory
466104		trxke01	Traffic (IOI10_traffic)	C++17	0 / 100	15 ms	27676 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);
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;
    // cout << "OG congestion of " << curr << " is " << cong[curr] << "\n";
    return congestion;
}

void dfs2(int curr, int prev, const int P[]){
    // test
    // cout << "testing " << curr << " congestion is " << cong[curr]-P[curr] << "\n";
    // cout << "testing min congestion is " << minCongestion << "\n";
    if(cong[curr]-P[curr] < minCongestion){
        minCongestion = cong[curr]-P[curr];
        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 = dfs1(0, -1, P)-P[0];

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

    // return
    return bestCity;
}

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