Submission #1025170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025170		gutzzy	Traffic (IOI10_traffic)	C++17	100 / 100	608 ms	170832 KiB

traffic

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

vector<ll> dp;
vector<vector<int>> lst;
pair<int,ll> ans;
ll total = 0;

ll dfs(int nodo, int padre, int *p){
    ll res = 0;
    dp[nodo] = p[nodo];
    for(auto vecino:lst[nodo]){
        if(vecino==padre) continue;
        dp[nodo] += dfs(vecino,nodo,p);
        res = max(res, dp[vecino]);
    }
    res = max(res,total-dp[nodo]);
    //cout << "arena: " << nodo << " res: " << res << endl;
    if(res<ans.second){
        //cout << "update!   new arena: " << nodo << " " << res << endl;
        ans.second = res;
        ans.first = nodo;
    }
    return dp[nodo];
    
}
 
int LocateCentre(int n, int *p, int *s, int *d){
    ans.first = 0;
    ans.second = 1e18;
    lst = vector<vector<int>>(n,vector<int>());
    dp = vector<ll>(n);
    for(int i=0;i<n-1;i++){
        lst[s[i]].push_back(d[i]);
        lst[d[i]].push_back(s[i]);
        total += p[i];
    }
    total += p[n-1];
    dfs(0,0,p);
    return ans.first;
    
}
 
/*
int main(){
    cout << LocateCentre(5,{10,10,10,20,20},{0,1,2,3},{2,2,3,4}) << endl;
 
    return 0;
}
*/
// vector<int>, int*

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