oj.uz

Submission #198468

# Submission time Handle Problem Language Result Execution time Memory
198468 2020-01-26T07:17:42 Z oolimry Cheap flights (LMIO18_pigus_skrydziai) C++14
16 / 100
 1707 ms 105212 KB 
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,long long> ii; 
static vector<ii> adj[500005];
static vector<ii> tree[500005];
map<ii, long long> thonk;
static int p[500005];
int numSets;
int findSet(int u){
	if(p[u] == u) return u;
	else{
		p[u] = findSet(p[u]);
		return p[u];
	}
}
 
bool unionSet(int u, int v){
	u = findSet(u);
	v = findSet(v);
	if(u == v) return false;
	p[u] = v;
	numSets--;
	return true;
}


struct edge{
	int u;
	int 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);
	int n, m; cin >> n >> m;
	edge edges[m];
	
	for(int i = 0;i < n;i++) p[i] = i;

	for(int i = 0;i < m;i++){
		int 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(int 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(int 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 21 ms 23800 KB Output is correct
2 Correct 20 ms 23800 KB Output is correct
3 Correct 21 ms 23800 KB Output is correct
4 Correct 23 ms 23780 KB Output is correct
5 Correct 24 ms 23800 KB Output is correct
6 Correct 54 ms 27560 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 23 ms 23800 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 21 ms 23800 KB Output is correct
2 Correct 20 ms 23800 KB Output is correct
3 Correct 21 ms 23800 KB Output is correct
4 Correct 23 ms 23780 KB Output is correct
5 Correct 24 ms 23800 KB Output is correct
6 Correct 54 ms 27560 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 23 ms 23800 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 492 ms 67380 KB Output is correct
2 Correct 1149 ms 99504 KB Output is correct
3 Correct 313 ms 48888 KB Output is correct
4 Correct 758 ms 74904 KB Output is correct
5 Correct 1707 ms 95444 KB Output is correct
6 Correct 160 ms 46696 KB Output is correct
7 Correct 359 ms 88116 KB Output is correct
8 Correct 427 ms 96764 KB Output is correct
9 Correct 28 ms 25208 KB Output is correct
10 Correct 151 ms 46712 KB Output is correct
11 Correct 399 ms 92428 KB Output is correct
12 Correct 411 ms 69624 KB Output is correct
13 Correct 26 ms 23800 KB Output is correct
14 Correct 382 ms 43360 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 67380 KB Output is correct
2 Correct 1149 ms 99504 KB Output is correct
3 Correct 313 ms 48888 KB Output is correct
4 Correct 758 ms 74904 KB Output is correct
5 Correct 1707 ms 95444 KB Output is correct
6 Correct 160 ms 46696 KB Output is correct
7 Correct 359 ms 88116 KB Output is correct
8 Correct 427 ms 96764 KB Output is correct
9 Correct 28 ms 25208 KB Output is correct
10 Correct 151 ms 46712 KB Output is correct
11 Correct 399 ms 92428 KB Output is correct
12 Correct 411 ms 69624 KB Output is correct
13 Correct 26 ms 23800 KB Output is correct
14 Correct 382 ms 43360 KB Output is correct
15 Correct 878 ms 67344 KB Output is correct
16 Correct 693 ms 63932 KB Output is correct
17 Correct 907 ms 73468 KB Output is correct
18 Correct 1181 ms 81168 KB Output is correct
19 Correct 348 ms 50036 KB Output is correct
20 Correct 1202 ms 85900 KB Output is correct
21 Correct 1245 ms 105212 KB Output is correct
22 Correct 948 ms 77808 KB Output is correct
23 Correct 833 ms 87904 KB Output is correct
24 Correct 640 ms 56628 KB Output is correct
25 Correct 1274 ms 86588 KB Output is correct
26 Correct 1456 ms 82756 KB Output is correct
27 Correct 1263 ms 79916 KB Output is correct
28 Correct 21 ms 23800 KB Output is correct
29 Correct 20 ms 23800 KB Output is correct
30 Correct 21 ms 23800 KB Output is correct
31 Correct 23 ms 23780 KB Output is correct
32 Correct 24 ms 23800 KB Output is correct
33 Correct 54 ms 27560 KB Output is correct
34 Correct 24 ms 23800 KB Output is correct
35 Correct 24 ms 23800 KB Output is correct
36 Correct 23 ms 23800 KB Output is correct
37 Incorrect 21 ms 23800 KB Output isn't correct
38 Halted 0 ms 0 KB -