Submission #1134130

#TimeUsernameProblemLanguageResultExecution timeMemory
1134130AvianshAesthetic (NOI20_aesthetic)C++20
0 / 100
125 ms25884 KiB
#include <bits/stdc++.h> using namespace std; int n,m; vector<int>fin; void dfs(int st,vector<array<int,3>>(&g)[],int p, vector<int>(&pars)){ if(st==n-1){ for(int i : pars){ fin.push_back(i); } return; } for(array<int,3>e:g[st]){ if(e[0]==p) continue; pars.push_back(e[2]); dfs(e[0],g,st,pars); assert(pars.back()==e[2]); pars.pop_back(); } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; assert(m==n-1); vector<array<int,3>>g[n]; array<int,3>edges[m]; for(int i = 0;i<m;i++){ cin >> edges[i][0]; cin >> edges[i][1]; cin >> edges[i][2]; edges[i][0]--; edges[i][1]--; g[edges[i][0]].push_back({edges[i][1],edges[i][2],i}); g[edges[i][1]].push_back({edges[i][0],edges[i][2],i}); } long long pref[m]; pref[m-1]=edges[m-1][2]; for(int i = m-2;i>=0;i--){ pref[i]=max(1LL*edges[i][2],pref[i+1]); } vector<int>temp; dfs(0,g,-1,temp); long long ans = 0; for(int i : fin){ ans+=edges[i][2]; } long long maxima = 0; for(int i : fin){ if(i!=n-1) maxima=max(maxima,pref[i+1]); } ans+=maxima; cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...