# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
337582 | 2020-12-21T06:56:17 Z | exopeng | Traffic (IOI10_traffic) | C++14 | 17 ms | 23916 KB |
#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]); } long long LocateCentre(int ns, int ps[], int ss[],int ds[]) { n=ns; 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]; } 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); } 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 ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23916 KB | Output is correct |
2 | Incorrect | 17 ms | 23916 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23916 KB | Output is correct |
2 | Incorrect | 17 ms | 23916 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23916 KB | Output is correct |
2 | Incorrect | 17 ms | 23916 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 23916 KB | Output is correct |
2 | Incorrect | 17 ms | 23916 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |