#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;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |
- |