Submission #501354

#	Time	Username	Problem	Language	Result	Execution time	Memory
501354		Iwanttobreakfree	Traffic (IOI10_traffic)	C++17	100 / 100	1000 ms	179960 KiB

traffic

#include <iostream>
#include <vector>
#include "traffic.h"
using namespace std;
typedef long long ll;
ll ans=1e18;
int node=-1;
ll dfs(int a,vector<vector<int> >& v,int par,ll tot,vector<int>& w){
    ll sol=0,parw=0;
    for(int x:v[a]){
        if(x!=par){
            ll af=dfs(x,v,a,tot,w);
            sol=max(sol,af);
            parw+=af;
        }
    }
    ll fin=max(sol,tot-parw-w[a]);
    if(fin<ans){
        ans=fin;
        node=a;
    }
    return parw+w[a];
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
    vector<vector<int> > v(N,vector<int>());
    vector<int> w(N);
    ll tot=0;
    for(int i=0;i<N;i++)w[i]=pp[i];
    for(int i=0;i<N-1;i++){
        v[S[i]].push_back(D[i]);
        v[D[i]].push_back(S[i]);
    }
    for(int i=0;i<N;i++)tot+=pp[i];
    dfs(0,v,-1,tot,w);
    return node;
}

/*int main(){
    int n;
    cin>>n;
    int pp[n],s[n],d[n];
    for(int i=0;i<n;i++)cin>>pp[i];
    for(int i=0;i<n-1;i++)cin>>s[i]>>d[i];
    cout<<LocateCentre(n,pp,s,d);
}*/

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