제출 #198473

#제출 시각아이디문제언어결과실행 시간메모리
198473oolimryCheap flights (LMIO18_pigus_skrydziai)C++14
28 / 100
2369 ms127852 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<long long,long long> ii; static vector<ii> adj[500005]; static vector<ii> tree[500005]; map<ii, long long> thonk; class UFDS { typedef vector<int> vi; public: vi p, rak, setSize; int numSets; void create(int n){ setSize.assign(n, 1); numSets = n; rak.assign(n, 0); p.assign(n, 0); for(int i =0;i < n;i++){ p[i] = i; } } int findSet(int i){ return (p[i] == i) ? i : (p[i] = findSet(p[i])); } bool isSameSet(int i, int j){ return findSet(i) == findSet(j); } bool unionSet(int i, int j){ if(isSameSet(i,j)) return false; numSets--; int x = findSet(i); int y = findSet(j); if(rak[x] > rak[y]) { p[y] = x; setSize[x] += setSize[y]; } else { p[x] = y; setSize[y] += setSize[x]; if(rak[x] == rak[y]) rak[y]++; } return true; } } uf; struct edge{ long long u; long long v; long long w; }; bool comp(edge a, edge b){ return a.w > b.w; } int main(){ //freopen("i.txt","r",stdin); ios_base::sync_with_stdio(false); cin.tie(0); long long n, m; cin >> n >> m; edge edges[m]; uf.create(n); for(long long i = 0;i < m;i++){ long long u, v; long long w; cin >> u >> v >> w; u--; v--; adj[u].push_back(ii(v,w)); adj[v].push_back(ii(u,w)); edges[i] = {u,v,w}; thonk[ii(u,v)] = w; thonk[ii(v,u)] = w; } long long ans = 0; for(long long i = 0;i < n;i++){ long long acc = 0; for(ii v : adj[i]) acc += v.second; ans = max(ans, acc); } sort(edges,edges+m,comp); for(edge e : edges){ if(uf.unionSet(e.u, e.v)){ tree[e.u].push_back(ii(e.v,e.w)); tree[e.v].push_back(ii(e.u,e.w)); } } if(n <= 200){ for(int b = 0;b < n;b++){ for(int c = 0;c < n;c++){ if(thonk.find(ii(b,c)) == thonk.end()) thonk[ii(b,c)] = -1238213829038LL; } } for(int a = 0;a < n;a++){ for(int b = 0;b < n;b++){ for(int c = 0;c < n;c++){ ans = max(ans, thonk[ii(a,b)] + thonk[ii(c,b)] + thonk[ii(a,c)]); } } } } for(long long i = 0;i < n;i++){ if(tree[i].size() == 2){ ii u = tree[i][0]; ii v = tree[i][1]; if(thonk.find(ii(u.first,v.first)) != thonk.end()){ ans = max(ans, u.second + v.second + thonk[ii(u.first,v.first)]); } } } 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...