제출 #373529

#제출 시각아이디문제언어결과실행 시간메모리
373529lakshith_Traffic (IOI10_traffic)C++14
50 / 100
1594 ms262148 KiB
#include <bits/stdc++.h> #include "traffic.h" #define pb push_back #define ll long long using namespace std; int P[1000000]; vector<vector<int>> adj(1000000,vector<int>()); map<pair<int,int>,ll> m; ll dp(int p,int c){ if(m.find((pair<int,int>){p,c})!=m.end())return m[(pair<int,int>){p,c}]; ll ans = P[c]; for(int v:adj[c]){ if(v==p)continue; ans += dp(c,v); } m.insert({{p,c},ans}); return ans; } int LocateCentre(int n,int p[],int s[],int d[]){ for(int i=0;i<n-1;i++){ adj.at(s[i]).pb(d[i]); adj.at(d[i]).pb(s[i]); } for(int i=0;i<n;i++)P[i]=p[i]; ll ans = LLONG_MAX; int index = -1; for(int i=0;i<n;i++){ ll local = LLONG_MIN; for(int v:adj[i])local = max(local,dp(i,v)); if(local<ans){ ans = local; index = i; } } return index; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...