Submission #205893

#	Time	Username	Problem	Language	Result	Execution time	Memory
205893		mraron	Cheap flights (LMIO18_pigus_skrydziai)	C++14	100 / 100	2992 ms	35704 KiB

pigus_skrydziai

#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef long long ll;

vector<pair<int, ll>> adj[300001];
ll cost(int a, int b) {
	if(adj[a].size()>adj[b].size()) swap(a,b);
	auto it=lower_bound(adj[a].begin(),adj[a].end(), make_pair(b,0LL));
	if(it==adj[a].end() || it->first!=b) return 0;
	return it->second;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;++i) {
		int a,b,c;
		cin>>a>>b>>c;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	ll ans=0;
	for(int i=1;i<=n;++i) {
		ll cans=0;
		for(auto j:adj[i]) {
			cans+=j.second;
		}
		ans=max(ans, cans);
		sort(adj[i].begin(),adj[i].end());
	}
	
	const int lim=200;
	for(int i=1;i<=n;++i) {
		if(adj[i].size()<=lim) {
			for(int j=0;j<adj[i].size();++j) {
				for(int k=j+1;k<adj[i].size();++k) {
					ans=max(ans, adj[i][j].second+adj[i][k].second+cost(adj[i][j].first, adj[i][k].first));
				}
			}
		}else {
			vector<int> kell(n+1);
			for(auto j:adj[i]) {
				kell[j.first]=j.second;
			}
			for(auto j:adj[i]) {
				for(auto k:adj[j.first]) {
					if(kell[k.first]) ans=max(ans, k.second+j.second+kell[k.first]);
				}
			}
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Compilation message (stderr)

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<adj[i].size();++j) {
                ~^~~~~~~~~~~~~~
pigus_skrydziai.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int k=j+1;k<adj[i].size();++k) {
                   ~^~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 25 / 25
• Subtask 3: 16 / 16
• Subtask 4: 47 / 47