| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 337578 | exopeng | Traffic (IOI10_traffic) | C++14 | 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 <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define f first
#define s second
#define pii pair<int,int>
#define pdd pair<double,double>
#define is insert
const long long INF = 1e16;
const long long MOD = 1e9+7;
const int MAXN = 1e6+10;
//store test cases here
/*
*/
int n;
int p[MAXN];
int s[MAXN];
int d[MAXN];
multiset<int,greater<int> > ms;
long long ans=INF;
vector<int> adj[MAXN];
long long ct[MAXN];
long long dfs(int v,int pa){
for(int i=0;i<adj[v].size();i++){
if(adj[v][i]!=pa){
ct[v]+=dfs(adj[v][i],v);
}
}
ms.is(ct[v]+p[v]);
return ct[v]+p[v];
}
void dfs1(int v,int pa){
long long temp=ct[pa];
long long temp1=ct[v];
ms.erase(ms.find(ct[v]+p[v]));
ct[pa]-=ct[v]+p[v];
ct[v]+=p[pa]+ct[pa];
ms.is(ct[pa]+p[pa]);
ans=min(ans,(long long)*ms.begin());
for(int i=0;i<adj[v].size();i++){
if(adj[v][i]!=pa){
dfs1(adj[v][i],v);
}
}
ms.erase(ms.find(ct[pa]+p[pa]));
ct[pa]=temp;
ct[v]=temp1;
ms.is(ct[v]+p[v]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin>>p[i];
}
for(int i=0;i<n-1;i++){
cin>>s[i]>>d[i];
adj[s[i]].pb(d[i]);
adj[d[i]].pb(s[i]);
}
for(int i=0;i<adj[0].size();i++){
ct[0]+=dfs(adj[0][i],0);
}
for(int i=0;i<n;i++){
//cout<<ct[i]<<"\n";
}
for(int i=0;i<adj[0].size();i++){
dfs1(adj[0][i],0);
}
cout<<ans<<"\n";
return 0;
}
/* REMINDERS
* STORE INFO IN VECTORS, NOT STRINGS!!!!!!!!!
* CHECK ARRAY BOUNDS, HOW BIG ARRAY HAS TO BE
* PLANNING!!!!!!!! Concrete plan before code
* IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
* IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
* IF CAN'T FIGURE ANYTHING OUT, MAKE TEN TEST CASES TO EVALUATE ALL TYPES OF SCENARIOS, THEN CONSTRUCT SOLUTION TO FIT IT
* NAIVE SOL FIRST TO CHECK AGAINST OPTIMIZED SOL
* MOD OUT EVERY STEP
* DON'T MAKE ASSUMPTIONS
* DON'T OVERCOMPLICATE
* CHECK INT VS LONG, IF YOU NEED TO STORE LARGE NUMBERS
* CHECK CONSTRAINTS, C <= N <= F...
* CHECK SPECIAL CASES, N = 1...
* TO TEST TLE/MLE, PLUG IN MAX VALS ALLOWED AND SEE WHAT HAPPENS
* ALSO CALCULATE BIG-O, OVERALL TIME COMPLEXITY
* IF ALL ELSE FAILS, DO CASEWORK
* compile with "g++ -std=c++11 filename.cpp" if using auto keyword
*/