oj.uz

답안 #205883

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205883 2020-03-01T09:47:22 Z mraron Cheap flights (LMIO18_pigus_skrydziai) C++14
12 / 100
 3000 ms 37048 KB 
#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=500;
	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: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.0 / 12.0

# 결과 실행 시간 메모리 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 10 ms 7416 KB Output is correct
6 Correct 267 ms 8688 KB Output is correct
7 Correct 10 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 9 ms 7420 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 7416 KB Output is correct
14 Correct 9 ms 7416 KB Output is correct
15 Correct 9 ms 7420 KB Output is correct
16 Correct 10 ms 7420 KB Output is correct
17 Correct 9 ms 7416 KB Output is correct
18 Correct 11 ms 7416 KB Output is correct
19 Correct 14 ms 7544 KB Output is correct
20 Correct 9 ms 7416 KB Output is correct
21 Correct 9 ms 7416 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 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 10 ms 7416 KB Output is correct
6 Correct 267 ms 8688 KB Output is correct
7 Correct 10 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 9 ms 7420 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 7416 KB Output is correct
14 Correct 9 ms 7416 KB Output is correct
15 Correct 9 ms 7420 KB Output is correct
16 Correct 10 ms 7420 KB Output is correct
17 Correct 9 ms 7416 KB Output is correct
18 Correct 11 ms 7416 KB Output is correct
19 Correct 14 ms 7544 KB Output is correct
20 Correct 9 ms 7416 KB Output is correct
21 Correct 9 ms 7416 KB Output is correct
22 Execution timed out 3070 ms 37048 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 19684 KB Output is correct
2 Correct 335 ms 29788 KB Output is correct
3 Correct 90 ms 14224 KB Output is correct
4 Correct 202 ms 20888 KB Output is correct
5 Correct 520 ms 29408 KB Output is correct
6 Execution timed out 3060 ms 13412 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 19684 KB Output is correct
2 Correct 335 ms 29788 KB Output is correct
3 Correct 90 ms 14224 KB Output is correct
4 Correct 202 ms 20888 KB Output is correct
5 Correct 520 ms 29408 KB Output is correct
6 Execution timed out 3060 ms 13412 KB Time limit exceeded
7 Halted 0 ms 0 KB -