oj.uz

Submission #205891

# Submission time Handle Problem Language Result Execution time Memory
205891 2020-03-01T09:55:26 Z mraron Cheap flights (LMIO18_pigus_skrydziai) C++14
28 / 100
 3000 ms 29304 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=2000;
	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 11 ms 7416 KB Output is correct
6 Correct 106 ms 8232 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 11 ms 7416 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 9 ms 7448 KB Output is correct
12 Correct 9 ms 7416 KB Output is correct
13 Correct 9 ms 7416 KB Output is correct
14 Correct 8 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 13 ms 7416 KB Output is correct
19 Correct 12 ms 7416 KB Output is correct
20 Correct 10 ms 7416 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 11 ms 7416 KB Output is correct
6 Correct 106 ms 8232 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 11 ms 7416 KB Output is correct
9 Correct 9 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 9 ms 7448 KB Output is correct
12 Correct 9 ms 7416 KB Output is correct
13 Correct 9 ms 7416 KB Output is correct
14 Correct 8 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 13 ms 7416 KB Output is correct
19 Correct 12 ms 7416 KB Output is correct
20 Correct 10 ms 7416 KB Output is correct
21 Correct 9 ms 7416 KB Output is correct
22 Execution timed out 3059 ms 29304 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 16760 KB Output is correct
2 Correct 291 ms 23032 KB Output is correct
3 Correct 83 ms 12664 KB Output is correct
4 Correct 190 ms 17716 KB Output is correct
5 Correct 367 ms 23032 KB Output is correct
6 Correct 1772 ms 11616 KB Output is correct
7 Correct 132 ms 19448 KB Output is correct
8 Correct 158 ms 21496 KB Output is correct
9 Correct 13 ms 7416 KB Output is correct
10 Correct 1752 ms 11552 KB Output is correct
11 Correct 133 ms 21596 KB Output is correct
12 Correct 1848 ms 15584 KB Output is correct
13 Correct 9 ms 7416 KB Output is correct
14 Correct 502 ms 11840 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 16760 KB Output is correct
2 Correct 291 ms 23032 KB Output is correct
3 Correct 83 ms 12664 KB Output is correct
4 Correct 190 ms 17716 KB Output is correct
5 Correct 367 ms 23032 KB Output is correct
6 Correct 1772 ms 11616 KB Output is correct
7 Correct 132 ms 19448 KB Output is correct
8 Correct 158 ms 21496 KB Output is correct
9 Correct 13 ms 7416 KB Output is correct
10 Correct 1752 ms 11552 KB Output is correct
11 Correct 133 ms 21596 KB Output is correct
12 Correct 1848 ms 15584 KB Output is correct
13 Correct 9 ms 7416 KB Output is correct
14 Correct 502 ms 11840 KB Output is correct
15 Correct 150 ms 17236 KB Output is correct
16 Correct 875 ms 15580 KB Output is correct
17 Correct 1907 ms 16488 KB Output is correct
18 Correct 1932 ms 17480 KB Output is correct
19 Correct 74 ms 12644 KB Output is correct
20 Execution timed out 3083 ms 23800 KB Time limit exceeded
21 Halted 0 ms 0 KB -