| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 533111 | avaneeshk098 | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "traffic.h"
#include <bits/stdc++.h>
#define ff first
#define int long long int
#define ss second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define max_size 100000000
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define w(t) int t; cin >> t; while(t--)
#define inf 1e18
#define MOD (int)1e9+7
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define range(a,b) substr(a,b-a+1)
#define mina(a,b,c) min(a, min(b, c))
#define maxa(a,b,c) max(a, max(b, c))
#define sz(a) (int)a.size()
#define endl '\n'
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define FOR(x,y) for(int i = x; i < y; i++)
// #define f(t) int t; cin >> t; for(int i = 1; i <= t; i++)
using namespace std;
const int MXN = (int)1e6 + 5;
int dp1[MXN];
int dp2[MXN];
vi adj[MXN];
int cost[MXN];
int dfs(int s, int t){
if(adj[s].size() == 1 && s != t){
return cost[s];
}
for(auto i : adj[s]){
if(i != t){
int val = dfs(i,s);
dp1[s] += val;
dp2[s] = max(dp2[s], val);
}
}
return dp1[s] + cost[s];
}
int LocateCentre(int n, int pp[], int s[], int d[]) {
int total = 0;
for(int i = 1; i <= n; i++){
cost[i] = pp[i-1];
total += cost[i];
}
for(int i = 0; i < n-1; i++){
adj[s[i]+1].pb(d[i]+1);
adj[d[i]+1].pb(s[i]+1);
}
dfs(1,1);
int ans = inf;
int fans;
for(int i = 1; i <= n; i++){
if(ans > max(total - dp1[i] - cost[i], dp2[i])){
ans = max(total - dp1[i] - cost[i], dp2[i]);
fans = i;
}
}
return fans - 1;
}