oj.uz

Submission #198470

# Submission time Handle Problem Language Result Execution time Memory
198470 2020-01-26T07:23:53 Z oolimry Cheap flights (LMIO18_pigus_skrydziai) C++14
16 / 100
 1549 ms 101660 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<long long,long long> ii; 
static vector<ii> adj[500005];
static vector<ii> tree[500005];
map<ii, long long> thonk;
static long long p[500005];

long long findSet(long long u){
	if(p[u] == u) return u;
	else{
		p[u] = findSet(p[u]);
		return p[u];
	}
}
 
bool unionSet(long long u, long long v){
	u = findSet(u);
	v = findSet(v);
	if(u == v) return false;
	p[u] = v;
	return true;
}


struct edge{
	long long u;
	long long v;
	long long w;
};

bool comp(edge a, edge b){
	return a.w > b.w;
}
int main(){
	//freopen("i.txt","r",stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	long long n, m; cin >> n >> m;
	edge edges[m];
	
	for(long long i = 0;i < n;i++) p[i] = i;

	for(long long i = 0;i < m;i++){
		long long u, v; long long w;
		cin >> u >> v >> w; u--; v--;
		adj[u].push_back(ii(v,w));
		adj[v].push_back(ii(u,w));
		edges[i] = {u,v,w};
		thonk[ii(u,v)] = w;
		thonk[ii(v,u)] = w;
	}
	
	long long ans = 0;
	
	for(long long i = 0;i < n;i++){
		long long acc = 0;
		for(ii v : adj[i]) acc += v.second;
		ans = max(ans, acc);
	}
	
	sort(edges,edges+m,comp);
	
	for(edge e : edges){
		if(unionSet(e.u, e.v)){
			tree[e.u].push_back(ii(e.v,e.w));
			tree[e.v].push_back(ii(e.u,e.w));
		}
	}
	
	for(long long i = 0;i < n;i++){
		if(tree[i].size() == 2){
			ii u = tree[i][0];
			ii v = tree[i][1];
			if(thonk.find(ii(u.first,v.first)) != thonk.end()){
				ans = max(ans, u.second + v.second + thonk[ii(u.first,v.first)]);
			}
		}
	}
	
	cout << ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 21 ms 23832 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 21 ms 23800 KB Output is correct
6 Correct 42 ms 27640 KB Output is correct
7 Correct 21 ms 23800 KB Output is correct
8 Correct 22 ms 23800 KB Output is correct
9 Correct 21 ms 23900 KB Output is correct
10 Incorrect 21 ms 23800 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 21 ms 23832 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 21 ms 23800 KB Output is correct
6 Correct 42 ms 27640 KB Output is correct
7 Correct 21 ms 23800 KB Output is correct
8 Correct 22 ms 23800 KB Output is correct
9 Correct 21 ms 23900 KB Output is correct
10 Incorrect 21 ms 23800 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 67448 KB Output is correct
2 Correct 1170 ms 98656 KB Output is correct
3 Correct 383 ms 48760 KB Output is correct
4 Correct 719 ms 74500 KB Output is correct
5 Correct 1549 ms 94228 KB Output is correct
6 Correct 157 ms 46760 KB Output is correct
7 Correct 346 ms 87336 KB Output is correct
8 Correct 392 ms 95900 KB Output is correct
9 Correct 28 ms 26488 KB Output is correct
10 Correct 154 ms 46580 KB Output is correct
11 Correct 431 ms 92252 KB Output is correct
12 Correct 314 ms 69240 KB Output is correct
13 Correct 22 ms 23800 KB Output is correct
14 Correct 275 ms 43132 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 67448 KB Output is correct
2 Correct 1170 ms 98656 KB Output is correct
3 Correct 383 ms 48760 KB Output is correct
4 Correct 719 ms 74500 KB Output is correct
5 Correct 1549 ms 94228 KB Output is correct
6 Correct 157 ms 46760 KB Output is correct
7 Correct 346 ms 87336 KB Output is correct
8 Correct 392 ms 95900 KB Output is correct
9 Correct 28 ms 26488 KB Output is correct
10 Correct 154 ms 46580 KB Output is correct
11 Correct 431 ms 92252 KB Output is correct
12 Correct 314 ms 69240 KB Output is correct
13 Correct 22 ms 23800 KB Output is correct
14 Correct 275 ms 43132 KB Output is correct
15 Correct 819 ms 66752 KB Output is correct
16 Correct 705 ms 61908 KB Output is correct
17 Correct 815 ms 71672 KB Output is correct
18 Correct 1114 ms 78744 KB Output is correct
19 Correct 272 ms 49512 KB Output is correct
20 Correct 1118 ms 83280 KB Output is correct
21 Correct 1229 ms 101660 KB Output is correct
22 Correct 761 ms 75768 KB Output is correct
23 Correct 868 ms 86768 KB Output is correct
24 Correct 518 ms 56380 KB Output is correct
25 Correct 1174 ms 83960 KB Output is correct
26 Correct 1120 ms 81832 KB Output is correct
27 Correct 1035 ms 78840 KB Output is correct
28 Correct 22 ms 23800 KB Output is correct
29 Correct 22 ms 23800 KB Output is correct
30 Correct 21 ms 23832 KB Output is correct
31 Correct 22 ms 23800 KB Output is correct
32 Correct 21 ms 23800 KB Output is correct
33 Correct 42 ms 27640 KB Output is correct
34 Correct 21 ms 23800 KB Output is correct
35 Correct 22 ms 23800 KB Output is correct
36 Correct 21 ms 23900 KB Output is correct
37 Incorrect 21 ms 23800 KB Output isn't correct
38 Halted 0 ms 0 KB -