| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 340655 | 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 = 2e9+10;
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;
int ans=INF;
int an=0;
vector<int> adj[MAXN];
int ct[MAXN];
int 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]));
int t2=ct[v]+p[v];
ct[pa]-=ct[v]+p[v];
ct[v]+=p[pa]+ct[pa];
ms.is(ct[pa]+p[pa]);
int t1=ct[pa]+p[pa];
if((int)*ms.begin()<ans){
ans=*ms.begin();
an=v;
}
for(int i=0;i<adj[v].size();i++){
if(adj[v][i]!=pa){
dfs1(adj[v][i],v);
}
}
ms.erase(ms.find(t1));
ct[pa]=temp;
ct[v]=temp1;
ms.is(t2);
}
long long LocateCentre(int ns, int ps[], int ss[],int ds[]) {
ms.clear();
ans=INF;
n=ns;
for(int i=0;i<n;i++){
adj[i].clear();
ct[i]=0;
}
for(int i=0;i<n;i++){
p[i]=ps[i];
}
for(int i=0;i<n-1;i++){
s[i]=ss[i];
d[i]=ds[i];
}
//handle n=1
if(n==1){
return 0;
}
for(int i=0;i<n-1;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);
}
ans=(int)*ms.begin();
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);
}
return an;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=0;i<n;i++){
cin>>p[i];
}
//handle n=1
if(n==1){
cout<<0<<"\n";
return 0;
}
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);
}
ans=min(ans,(int)*ms.begin());
for(int i=0;i<adj[0].size();i++){
dfs1(adj[0][i],0);
}
cout<<an<<"\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
*/