답안 #906450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
906450	2024-01-14T10:06:30 Z	pcc	Cheap flights (LMIO18_pigus_skrydziai)	C++14	53 / 100	2822 ms	87032 KB

pigus_skrydziai

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 3e5+10;
const int lim = 2.5*CLOCKS_PER_SEC;
int N,M;
unordered_map<int,ll> mp[mxn];
vector<tlll> edges;
ll sum[mxn];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int st = clock();
	cin>>N>>M;
	for(int i = 0;i<M;i++){
		int a,b,c;
		cin>>a>>b>>c;
		mp[a][b] = c;
		mp[b][a] = c;
		sum[a] += c;
		sum[b] += c;
		edges.push_back(make_tuple(a,b,c));
	}
	random_shuffle(edges.begin(),edges.end());
	ll ans = *max_element(sum,sum+N+1);
	for(auto &i:edges){
		int a = get<0>(i),b = get<1>(i),ts = get<2>(i);
		if(mp[a].size()>mp[b].size())swap(a,b);
		for(auto &j:mp[a]){
			if(clock()-st>=lim)break;
			if(mp[b].find(j.fs) != mp[b].end()){
				ans = max(ans,mp[b][j.fs]+j.sc+ts);
			}
		}
		if(clock()-st>=lim)break;
	}
	cout<<ans;
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	16984 KB	Output is correct
2	Correct	6 ms	16988 KB	Output is correct
3	Correct	5 ms	16988 KB	Output is correct
4	Correct	6 ms	16832 KB	Output is correct
5	Correct	6 ms	16988 KB	Output is correct
6	Correct	1308 ms	19092 KB	Output is correct
7	Correct	6 ms	16984 KB	Output is correct
8	Correct	7 ms	16984 KB	Output is correct
9	Correct	6 ms	16988 KB	Output is correct
10	Correct	6 ms	17032 KB	Output is correct
11	Correct	8 ms	16988 KB	Output is correct
12	Correct	6 ms	16988 KB	Output is correct
13	Correct	6 ms	17068 KB	Output is correct
14	Correct	5 ms	16984 KB	Output is correct
15	Correct	6 ms	16984 KB	Output is correct
16	Correct	6 ms	16988 KB	Output is correct
17	Correct	6 ms	16988 KB	Output is correct
18	Correct	13 ms	16984 KB	Output is correct
19	Correct	19 ms	17244 KB	Output is correct
20	Correct	6 ms	16984 KB	Output is correct
21	Correct	5 ms	16988 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	16984 KB	Output is correct
2	Correct	6 ms	16988 KB	Output is correct
3	Correct	5 ms	16988 KB	Output is correct
4	Correct	6 ms	16832 KB	Output is correct
5	Correct	6 ms	16988 KB	Output is correct
6	Correct	1308 ms	19092 KB	Output is correct
7	Correct	6 ms	16984 KB	Output is correct
8	Correct	7 ms	16984 KB	Output is correct
9	Correct	6 ms	16988 KB	Output is correct
10	Correct	6 ms	17032 KB	Output is correct
11	Correct	8 ms	16988 KB	Output is correct
12	Correct	6 ms	16988 KB	Output is correct
13	Correct	6 ms	17068 KB	Output is correct
14	Correct	5 ms	16984 KB	Output is correct
15	Correct	6 ms	16984 KB	Output is correct
16	Correct	6 ms	16988 KB	Output is correct
17	Correct	6 ms	16988 KB	Output is correct
18	Correct	13 ms	16984 KB	Output is correct
19	Correct	19 ms	17244 KB	Output is correct
20	Correct	6 ms	16984 KB	Output is correct
21	Correct	5 ms	16988 KB	Output is correct
22	Correct	2822 ms	70120 KB	Output is correct
23	Correct	2582 ms	77292 KB	Output is correct
24	Correct	281 ms	19468 KB	Output is correct
25	Correct	35 ms	17756 KB	Output is correct
26	Correct	36 ms	17756 KB	Output is correct
27	Correct	11 ms	17244 KB	Output is correct
28	Correct	2559 ms	42628 KB	Output is correct
29	Correct	2525 ms	26896 KB	Output is correct
30	Correct	2542 ms	31900 KB	Output is correct
31	Correct	8 ms	16988 KB	Output is correct
32	Correct	7 ms	16988 KB	Output is correct
33	Correct	2559 ms	75940 KB	Output is correct
34	Correct	2557 ms	70344 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	333 ms	66064 KB	Output is correct
2	Correct	981 ms	81124 KB	Output is correct
3	Correct	263 ms	39420 KB	Output is correct
4	Correct	533 ms	58360 KB	Output is correct
5	Correct	1266 ms	70132 KB	Output is correct
6	Correct	2528 ms	29692 KB	Output is correct
7	Correct	527 ms	69304 KB	Output is correct
8	Correct	677 ms	78612 KB	Output is correct
9	Correct	8 ms	19744 KB	Output is correct
10	Correct	2535 ms	29716 KB	Output is correct
11	Correct	581 ms	68736 KB	Output is correct
12	Correct	2554 ms	42740 KB	Output is correct
13	Correct	6 ms	16988 KB	Output is correct
14	Correct	2521 ms	27528 KB	Output is correct

Subtask #4
0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	333 ms	66064 KB	Output is correct
2	Correct	981 ms	81124 KB	Output is correct
3	Correct	263 ms	39420 KB	Output is correct
4	Correct	533 ms	58360 KB	Output is correct
5	Correct	1266 ms	70132 KB	Output is correct
6	Correct	2528 ms	29692 KB	Output is correct
7	Correct	527 ms	69304 KB	Output is correct
8	Correct	677 ms	78612 KB	Output is correct
9	Correct	8 ms	19744 KB	Output is correct
10	Correct	2535 ms	29716 KB	Output is correct
11	Correct	581 ms	68736 KB	Output is correct
12	Correct	2554 ms	42740 KB	Output is correct
13	Correct	6 ms	16988 KB	Output is correct
14	Correct	2521 ms	27528 KB	Output is correct
15	Correct	6 ms	16984 KB	Output is correct
16	Correct	6 ms	16988 KB	Output is correct
17	Correct	5 ms	16988 KB	Output is correct
18	Correct	6 ms	16832 KB	Output is correct
19	Correct	6 ms	16988 KB	Output is correct
20	Correct	1308 ms	19092 KB	Output is correct
21	Correct	6 ms	16984 KB	Output is correct
22	Correct	7 ms	16984 KB	Output is correct
23	Correct	6 ms	16988 KB	Output is correct
24	Correct	6 ms	17032 KB	Output is correct
25	Correct	8 ms	16988 KB	Output is correct
26	Correct	6 ms	16988 KB	Output is correct
27	Correct	6 ms	17068 KB	Output is correct
28	Correct	5 ms	16984 KB	Output is correct
29	Correct	6 ms	16984 KB	Output is correct
30	Correct	6 ms	16988 KB	Output is correct
31	Correct	6 ms	16988 KB	Output is correct
32	Correct	13 ms	16984 KB	Output is correct
33	Correct	19 ms	17244 KB	Output is correct
34	Correct	6 ms	16984 KB	Output is correct
35	Correct	5 ms	16988 KB	Output is correct
36	Correct	2822 ms	70120 KB	Output is correct
37	Correct	2582 ms	77292 KB	Output is correct
38	Correct	281 ms	19468 KB	Output is correct
39	Correct	35 ms	17756 KB	Output is correct
40	Correct	36 ms	17756 KB	Output is correct
41	Correct	11 ms	17244 KB	Output is correct
42	Correct	2559 ms	42628 KB	Output is correct
43	Correct	2525 ms	26896 KB	Output is correct
44	Correct	2542 ms	31900 KB	Output is correct
45	Correct	8 ms	16988 KB	Output is correct
46	Correct	7 ms	16988 KB	Output is correct
47	Correct	2559 ms	75940 KB	Output is correct
48	Correct	2557 ms	70344 KB	Output is correct
49	Correct	562 ms	48616 KB	Output is correct
50	Correct	2556 ms	41716 KB	Output is correct
51	Correct	2624 ms	57060 KB	Output is correct
52	Correct	2641 ms	61388 KB	Output is correct
53	Correct	219 ms	41740 KB	Output is correct
54	Correct	2637 ms	58860 KB	Output is correct
55	Correct	883 ms	87032 KB	Output is correct
56	Correct	564 ms	62712 KB	Output is correct
57	Correct	646 ms	75196 KB	Output is correct
58	Correct	472 ms	44796 KB	Output is correct
59	Correct	2462 ms	60708 KB	Output is correct
60	Correct	2620 ms	58868 KB	Output is correct
61	Incorrect	2635 ms	56932 KB	Output isn't correct
62	Halted	0 ms	0 KB	-

답안 #906450

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 25.0 / 25.0

Subtask #3 16.0 / 16.0

Subtask #4 0 / 47.0

Subtask #1
12.0 / 12.0

Subtask #2
25.0 / 25.0

Subtask #3
16.0 / 16.0

Subtask #4
0 / 47.0