oj.uz

Submission #205889

# Submission time Handle Problem Language Result Execution time Memory
205889 2020-03-01T09:54:48 Z mraron Cheap flights (LMIO18_pigus_skrydziai) C++14
28 / 100
 3000 ms 29432 KB 
#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=1500;
	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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 97 ms 8184 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 10 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Correct 10 ms 7416 KB Output is correct
13 Correct 10 ms 7420 KB Output is correct
14 Correct 9 ms 7416 KB Output is correct
15 Correct 9 ms 7416 KB Output is correct
16 Correct 10 ms 7416 KB Output is correct
17 Correct 9 ms 7416 KB Output is correct
18 Correct 11 ms 7416 KB Output is correct
19 Correct 12 ms 7416 KB Output is correct
20 Correct 9 ms 7420 KB Output is correct
21 Correct 9 ms 7416 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7416 KB Output is correct
6 Correct 97 ms 8184 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 10 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 9 ms 7416 KB Output is correct
12 Correct 10 ms 7416 KB Output is correct
13 Correct 10 ms 7420 KB Output is correct
14 Correct 9 ms 7416 KB Output is correct
15 Correct 9 ms 7416 KB Output is correct
16 Correct 10 ms 7416 KB Output is correct
17 Correct 9 ms 7416 KB Output is correct
18 Correct 11 ms 7416 KB Output is correct
19 Correct 12 ms 7416 KB Output is correct
20 Correct 9 ms 7420 KB Output is correct
21 Correct 9 ms 7416 KB Output is correct
22 Execution timed out 3078 ms 29432 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 16760 KB Output is correct
2 Correct 310 ms 23096 KB Output is correct
3 Correct 76 ms 12668 KB Output is correct
4 Correct 165 ms 17704 KB Output is correct
5 Correct 365 ms 23180 KB Output is correct
6 Correct 1700 ms 11640 KB Output is correct
7 Correct 127 ms 19448 KB Output is correct
8 Correct 148 ms 21496 KB Output is correct
9 Correct 12 ms 7416 KB Output is correct
10 Correct 1713 ms 11540 KB Output is correct
11 Correct 135 ms 21596 KB Output is correct
12 Correct 1793 ms 15608 KB Output is correct
13 Correct 10 ms 7416 KB Output is correct
14 Correct 511 ms 11896 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 16760 KB Output is correct
2 Correct 310 ms 23096 KB Output is correct
3 Correct 76 ms 12668 KB Output is correct
4 Correct 165 ms 17704 KB Output is correct
5 Correct 365 ms 23180 KB Output is correct
6 Correct 1700 ms 11640 KB Output is correct
7 Correct 127 ms 19448 KB Output is correct
8 Correct 148 ms 21496 KB Output is correct
9 Correct 12 ms 7416 KB Output is correct
10 Correct 1713 ms 11540 KB Output is correct
11 Correct 135 ms 21596 KB Output is correct
12 Correct 1793 ms 15608 KB Output is correct
13 Correct 10 ms 7416 KB Output is correct
14 Correct 511 ms 11896 KB Output is correct
15 Correct 153 ms 17236 KB Output is correct
16 Correct 813 ms 15600 KB Output is correct
17 Correct 1862 ms 16484 KB Output is correct
18 Correct 1863 ms 17480 KB Output is correct
19 Correct 76 ms 12644 KB Output is correct
20 Execution timed out 3078 ms 23928 KB Time limit exceeded
21 Halted 0 ms 0 KB -