oj.uz

Submission #498294

# Submission time Handle Problem Language Result Execution time Memory
498294 2021-12-24T22:24:33 Z s_samchenko Cheap flights (LMIO18_pigus_skrydziai) C++17
100 / 100
 1343 ms 83896 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define vi vector <int>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 2e5+100;

void solve(){
	int n, m;
	cin >> n >> m;
	map <pii, int> e;
	vector <vector <pii> > g(n+10);
	for (int i = 0; i < m; ++i){
		int a, b, w; cin >> a >> b >> w;
		g[a].pb({w, b});
		g[b].pb({w, a});
		e[{a, b}] = w;
		e[{b, a}] = w;
	}
	
	int ans = 0;
	for (int v = 1; v <= n; ++v){
		sort(rall(g[v]));
		int res = 0;
		for (auto i : g[v]) res += i.ff;
		
		if (g[v].size() > 1){
			auto x = g[v][0], y = g[v][1];
			res = max(res, x.ff + y.ff + e[{x.ss, y.ss}]);
		}
		ans = max(ans, res);
	}
	
	cout << ans;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;

	while (tt--){
		solve();
		cout << '\n';
	}
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 15 ms 3600 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
21 Correct 0 ms 204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 15 ms 3600 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 2 ms 588 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1343 ms 83896 KB Output is correct
23 Correct 479 ms 79136 KB Output is correct
24 Correct 27 ms 3908 KB Output is correct
25 Correct 8 ms 1360 KB Output is correct
26 Correct 6 ms 1372 KB Output is correct
27 Correct 4 ms 716 KB Output is correct
28 Correct 419 ms 33696 KB Output is correct
29 Correct 112 ms 13684 KB Output is correct
30 Correct 217 ms 19944 KB Output is correct
31 Correct 1 ms 432 KB Output is correct
32 Correct 1 ms 456 KB Output is correct
33 Correct 491 ms 82120 KB Output is correct
34 Correct 393 ms 75588 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 35520 KB Output is correct
2 Correct 681 ms 79120 KB Output is correct
3 Correct 182 ms 26520 KB Output is correct
4 Correct 370 ms 50908 KB Output is correct
5 Correct 1038 ms 68116 KB Output is correct
6 Correct 88 ms 20048 KB Output is correct
7 Correct 262 ms 60996 KB Output is correct
8 Correct 230 ms 59060 KB Output is correct
9 Correct 6 ms 7484 KB Output is correct
10 Correct 85 ms 20104 KB Output is correct
11 Correct 317 ms 57908 KB Output is correct
12 Correct 204 ms 39852 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 183 ms 17048 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 35520 KB Output is correct
2 Correct 681 ms 79120 KB Output is correct
3 Correct 182 ms 26520 KB Output is correct
4 Correct 370 ms 50908 KB Output is correct
5 Correct 1038 ms 68116 KB Output is correct
6 Correct 88 ms 20048 KB Output is correct
7 Correct 262 ms 60996 KB Output is correct
8 Correct 230 ms 59060 KB Output is correct
9 Correct 6 ms 7484 KB Output is correct
10 Correct 85 ms 20104 KB Output is correct
11 Correct 317 ms 57908 KB Output is correct
12 Correct 204 ms 39852 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 183 ms 17048 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 15 ms 3600 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 0 ms 332 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 0 ms 204 KB Output is correct
30 Correct 0 ms 204 KB Output is correct
31 Correct 0 ms 204 KB Output is correct
32 Correct 1 ms 460 KB Output is correct
33 Correct 2 ms 588 KB Output is correct
34 Correct 0 ms 332 KB Output is correct
35 Correct 0 ms 204 KB Output is correct
36 Correct 1343 ms 83896 KB Output is correct
37 Correct 479 ms 79136 KB Output is correct
38 Correct 27 ms 3908 KB Output is correct
39 Correct 8 ms 1360 KB Output is correct
40 Correct 6 ms 1372 KB Output is correct
41 Correct 4 ms 716 KB Output is correct
42 Correct 419 ms 33696 KB Output is correct
43 Correct 112 ms 13684 KB Output is correct
44 Correct 217 ms 19944 KB Output is correct
45 Correct 1 ms 432 KB Output is correct
46 Correct 1 ms 456 KB Output is correct
47 Correct 491 ms 82120 KB Output is correct
48 Correct 393 ms 75588 KB Output is correct
49 Correct 436 ms 37856 KB Output is correct
50 Correct 430 ms 33408 KB Output is correct
51 Correct 476 ms 39592 KB Output is correct
52 Correct 687 ms 47796 KB Output is correct
53 Correct 157 ms 20824 KB Output is correct
54 Correct 677 ms 52536 KB Output is correct
55 Correct 676 ms 79104 KB Output is correct
56 Correct 423 ms 52804 KB Output is correct
57 Correct 494 ms 52396 KB Output is correct
58 Correct 314 ms 28300 KB Output is correct
59 Correct 759 ms 55324 KB Output is correct
60 Correct 674 ms 50992 KB Output is correct
61 Correct 636 ms 48224 KB Output is correct