답안 #205893

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
205893	2020-03-01T09:56:45 Z	mraron	Cheap flights (LMIO18_pigus_skrydziai)	C++14	100 / 100	2992 ms	35704 KB

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

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

#	결과	실행 시간	메모리	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	102 ms	8312 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	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	9 ms	7416 KB	Output is correct
13	Correct	9 ms	7416 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	7420 KB	Output is correct
18	Correct	11 ms	7416 KB	Output is correct
19	Correct	11 ms	7416 KB	Output is correct
20	Correct	9 ms	7416 KB	Output is correct
21	Correct	9 ms	7416 KB	Output is correct

Subtask #2
25.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	102 ms	8312 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	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	9 ms	7416 KB	Output is correct
13	Correct	9 ms	7416 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	7420 KB	Output is correct
18	Correct	11 ms	7416 KB	Output is correct
19	Correct	11 ms	7416 KB	Output is correct
20	Correct	9 ms	7416 KB	Output is correct
21	Correct	9 ms	7416 KB	Output is correct
22	Correct	2992 ms	29432 KB	Output is correct
23	Correct	2287 ms	32248 KB	Output is correct
24	Correct	47 ms	8696 KB	Output is correct
25	Correct	14 ms	7800 KB	Output is correct
26	Correct	15 ms	7800 KB	Output is correct
27	Correct	11 ms	7544 KB	Output is correct
28	Correct	269 ms	19764 KB	Output is correct
29	Correct	141 ms	12152 KB	Output is correct
30	Correct	295 ms	13944 KB	Output is correct
31	Correct	10 ms	7416 KB	Output is correct
32	Correct	10 ms	7416 KB	Output is correct
33	Correct	814 ms	35704 KB	Output is correct
34	Correct	713 ms	31608 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	110 ms	16764 KB	Output is correct
2	Correct	282 ms	23032 KB	Output is correct
3	Correct	73 ms	12664 KB	Output is correct
4	Correct	174 ms	17656 KB	Output is correct
5	Correct	385 ms	23032 KB	Output is correct
6	Correct	259 ms	11640 KB	Output is correct
7	Correct	124 ms	19576 KB	Output is correct
8	Correct	152 ms	21500 KB	Output is correct
9	Correct	12 ms	7416 KB	Output is correct
10	Correct	230 ms	11512 KB	Output is correct
11	Correct	132 ms	21596 KB	Output is correct
12	Correct	304 ms	15476 KB	Output is correct
13	Correct	9 ms	7416 KB	Output is correct
14	Correct	489 ms	11896 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	110 ms	16764 KB	Output is correct
2	Correct	282 ms	23032 KB	Output is correct
3	Correct	73 ms	12664 KB	Output is correct
4	Correct	174 ms	17656 KB	Output is correct
5	Correct	385 ms	23032 KB	Output is correct
6	Correct	259 ms	11640 KB	Output is correct
7	Correct	124 ms	19576 KB	Output is correct
8	Correct	152 ms	21500 KB	Output is correct
9	Correct	12 ms	7416 KB	Output is correct
10	Correct	230 ms	11512 KB	Output is correct
11	Correct	132 ms	21596 KB	Output is correct
12	Correct	304 ms	15476 KB	Output is correct
13	Correct	9 ms	7416 KB	Output is correct
14	Correct	489 ms	11896 KB	Output is correct
15	Correct	143 ms	17236 KB	Output is correct
16	Correct	233 ms	15704 KB	Output is correct
17	Correct	367 ms	16484 KB	Output is correct
18	Correct	388 ms	17480 KB	Output is correct
19	Correct	72 ms	12648 KB	Output is correct
20	Correct	667 ms	23800 KB	Output is correct
21	Correct	294 ms	23032 KB	Output is correct
22	Correct	186 ms	17784 KB	Output is correct
23	Correct	205 ms	20188 KB	Output is correct
24	Correct	94 ms	14284 KB	Output is correct
25	Correct	347 ms	21752 KB	Output is correct
26	Correct	233 ms	20656 KB	Output is correct
27	Correct	396 ms	19188 KB	Output is correct
28	Correct	9 ms	7416 KB	Output is correct
29	Correct	9 ms	7416 KB	Output is correct
30	Correct	9 ms	7416 KB	Output is correct
31	Correct	9 ms	7416 KB	Output is correct
32	Correct	10 ms	7416 KB	Output is correct
33	Correct	102 ms	8312 KB	Output is correct
34	Correct	10 ms	7416 KB	Output is correct
35	Correct	9 ms	7416 KB	Output is correct
36	Correct	9 ms	7416 KB	Output is correct
37	Correct	9 ms	7416 KB	Output is correct
38	Correct	9 ms	7416 KB	Output is correct
39	Correct	9 ms	7416 KB	Output is correct
40	Correct	9 ms	7416 KB	Output is correct
41	Correct	9 ms	7416 KB	Output is correct
42	Correct	9 ms	7416 KB	Output is correct
43	Correct	10 ms	7416 KB	Output is correct
44	Correct	9 ms	7420 KB	Output is correct
45	Correct	11 ms	7416 KB	Output is correct
46	Correct	11 ms	7416 KB	Output is correct
47	Correct	9 ms	7416 KB	Output is correct
48	Correct	9 ms	7416 KB	Output is correct
49	Correct	2992 ms	29432 KB	Output is correct
50	Correct	2287 ms	32248 KB	Output is correct
51	Correct	47 ms	8696 KB	Output is correct
52	Correct	14 ms	7800 KB	Output is correct
53	Correct	15 ms	7800 KB	Output is correct
54	Correct	11 ms	7544 KB	Output is correct
55	Correct	269 ms	19764 KB	Output is correct
56	Correct	141 ms	12152 KB	Output is correct
57	Correct	295 ms	13944 KB	Output is correct
58	Correct	10 ms	7416 KB	Output is correct
59	Correct	10 ms	7416 KB	Output is correct
60	Correct	814 ms	35704 KB	Output is correct
61	Correct	713 ms	31608 KB	Output is correct

답안 #205893

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 25.0 / 25.0

Subtask #3 16.0 / 16.0

Subtask #4 47.0 / 47.0

Subtask #1
12.0 / 12.0

Subtask #2
25.0 / 25.0

Subtask #3
16.0 / 16.0

Subtask #4
47.0 / 47.0