Submission #205878

#	Time	Username	Problem	Language	Result	Execution time	Memory
205878		mraron	Cheap flights (LMIO18_pigus_skrydziai)	C++14	12 / 100	3061 ms	45824 KiB

pigus_skrydziai

#include<bits/stdc++.h>
using namespace std;
int n,m;
typedef long long ll;
struct el {
	int a,b;
	ll c;
	bool operator<(const el& masik) const {
		if(a==masik.a) return b<masik.b;
		return a<masik.a;
	}
};
vector<el> lst;
vector<pair<int, ll>> adj[300001];
ll cost(int a, int b) {
	if(a>b) swap(a,b);
	auto it=lower_bound(lst.begin(),lst.end(), el{a,b,0});
	if(it==lst.end() || it->a!=a || it->b!=b) return 0;
	return it->c;
}
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;
		lst.push_back({min(a,b),max(a,b),c});
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	sort(lst.begin(),lst.end());
	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);
	}
	
	const int lim=sqrt(300000);
	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 i:adj[i]) {
				kell[i.first]=i.second;
			}
			for(auto i:lst) {
				if(kell[i.a] && kell[i.b]) ans=max(ans, kell[i.a]+kell[i.b]+i.c);
			}
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Compilation message (stderr)

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<adj[i].size();++j) {
                ~^~~~~~~~~~~~~~
pigus_skrydziai.cpp:47: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: 0 / 25
• Subtask 3: 0 / 16
• Subtask 4: 0 / 47