Submission #466102

#	Time	Username	Problem	Language	Result	Execution time	Memory
466102		trxke01	Traffic (IOI10_traffic)	C++17	0 / 100	35 ms	47940 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;
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){
    // test
    if(cong[curr] < minCongestion){
        bestCity = curr;
    }
    for(int next : adj[curr]){
        if(next != prev){
            // reroot
            cong[curr] -= cong[next];
            cong[next] += cong[curr];
            // go
            dfs2(next, curr);
            // 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);

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

    // output
    cout << bestCity << "\n";
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
   62 | }
      | ^

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