Submission #1236106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236106		islam_2010	Traffic (IOI10_traffic)	C++20	0 / 100	12 ms	27716 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

const int sz = 1e6+6;

vector<int> g[sz];
vector<int> sub(sz);
int s = 0;
int mn = 2e9+5;
int city=0;
void dfs(int node, int p){

    int mx = 0;
    for(auto i: g[node]){
        if(i!=p){
            dfs(i, node);
        }sub[node] += sub[i];
        mx = max(mx, sub[i]);

    }if(node!=0){
        mx=max(mx, s-sub[node]);
    }
    
    if(mn > mx){
        mn=mx;
        city=node;
    }

}

int LocateCentre(int n, int P[], int S[], int D[]){
    for(int i = 0; i < n-1; i++){
        g[S[i]].push_back(D[i]);
        g[D[i]].push_back(S[i]);
    }for(int i = 0; i < n; i++){
        s += P[i];
        sub[i] = P[i];
    }dfs(0, -1);
    return city;
}

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