Submission #906448

#TimeUsernameProblemLanguageResultExecution timeMemory
906448pccCheap flights (LMIO18_pigus_skrydziai)C++14
28 / 100
3039 ms81560 KiB
#include <bits/stdc++.h> #include <bits/extc++.h> using namespace __gnu_pbds; using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,popcnt") #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int mxn = 3e5+10; const int lim = 2.95*CLOCKS_PER_SEC; int N,M; unordered_map<int,ll> mp[mxn]; vector<tlll> edges; ll sum[mxn]; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int st = clock(); cin>>N>>M; for(int i = 0;i<M;i++){ int a,b,c; cin>>a>>b>>c; mp[a][b] = c; mp[b][a] = c; sum[a] += c; sum[b] += c; edges.push_back(make_tuple(a,b,c)); } random_shuffle(edges.begin(),edges.end()); ll ans = *max_element(sum,sum+N+1); for(auto &i:edges){ int a = get<0>(i),b = get<1>(i),ts = get<2>(i); if(mp[a].size()>mp[b].size())swap(a,b); for(auto &j:mp[a]){ if(clock()-st>=lim)break; if(mp[b].find(j.fs) != mp[b].end()){ ans = max(ans,mp[b][j.fs]+j.sc+ts); } } if(clock()-st>=lim)break; } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...