#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;
class UFDS {
typedef vector<int> vi;
public:
vi p, rak, setSize;
int numSets;
void create(int n){
setSize.assign(n, 1);
numSets = n;
rak.assign(n, 0);
p.assign(n, 0);
for(int i =0;i < n;i++){
p[i] = i;
}
}
int findSet(int i){
return (p[i] == i) ? i : (p[i] = findSet(p[i]));
}
bool isSameSet(int i, int j){
return findSet(i) == findSet(j);
}
bool unionSet(int i, int j){
if(isSameSet(i,j))
return false;
numSets--;
int x = findSet(i);
int y = findSet(j);
if(rak[x] > rak[y]) {
p[y] = x; setSize[x] += setSize[y];
}
else {
p[x] = y; setSize[y] += setSize[x];
if(rak[x] == rak[y]) rak[y]++;
}
return true;
}
} uf;
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];
uf.create(n);
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(uf.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));
}
}
if(n <= 200){
for(int b = 0;b < n;b++){
for(int c = 0;c < n;c++){
if(thonk.find(ii(b,c)) == thonk.end()) thonk[ii(b,c)] = -1238213829038LL;
}
}
for(int a = 0;a < n;a++){
for(int b = 0;b < n;b++){
for(int c = 0;c < n;c++){
ans = max(ans, thonk[ii(a,b)] + thonk[ii(c,b)] + thonk[ii(a,c)]);
}
}
}
}
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;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
22 ms |
23796 KB |
Output is correct |
5 |
Correct |
22 ms |
23800 KB |
Output is correct |
6 |
Correct |
1767 ms |
27676 KB |
Output is correct |
7 |
Correct |
20 ms |
23800 KB |
Output is correct |
8 |
Correct |
21 ms |
23800 KB |
Output is correct |
9 |
Correct |
25 ms |
23928 KB |
Output is correct |
10 |
Correct |
25 ms |
23928 KB |
Output is correct |
11 |
Correct |
1478 ms |
25976 KB |
Output is correct |
12 |
Correct |
834 ms |
25336 KB |
Output is correct |
13 |
Correct |
1469 ms |
25916 KB |
Output is correct |
14 |
Correct |
21 ms |
23800 KB |
Output is correct |
15 |
Correct |
20 ms |
23800 KB |
Output is correct |
16 |
Correct |
21 ms |
23800 KB |
Output is correct |
17 |
Correct |
22 ms |
23800 KB |
Output is correct |
18 |
Correct |
253 ms |
24696 KB |
Output is correct |
19 |
Correct |
2089 ms |
26532 KB |
Output is correct |
20 |
Correct |
1494 ms |
25976 KB |
Output is correct |
21 |
Correct |
21 ms |
23800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
22 ms |
23796 KB |
Output is correct |
5 |
Correct |
22 ms |
23800 KB |
Output is correct |
6 |
Correct |
1767 ms |
27676 KB |
Output is correct |
7 |
Correct |
20 ms |
23800 KB |
Output is correct |
8 |
Correct |
21 ms |
23800 KB |
Output is correct |
9 |
Correct |
25 ms |
23928 KB |
Output is correct |
10 |
Correct |
25 ms |
23928 KB |
Output is correct |
11 |
Correct |
1478 ms |
25976 KB |
Output is correct |
12 |
Correct |
834 ms |
25336 KB |
Output is correct |
13 |
Correct |
1469 ms |
25916 KB |
Output is correct |
14 |
Correct |
21 ms |
23800 KB |
Output is correct |
15 |
Correct |
20 ms |
23800 KB |
Output is correct |
16 |
Correct |
21 ms |
23800 KB |
Output is correct |
17 |
Correct |
22 ms |
23800 KB |
Output is correct |
18 |
Correct |
253 ms |
24696 KB |
Output is correct |
19 |
Correct |
2089 ms |
26532 KB |
Output is correct |
20 |
Correct |
1494 ms |
25976 KB |
Output is correct |
21 |
Correct |
21 ms |
23800 KB |
Output is correct |
22 |
Correct |
2170 ms |
127852 KB |
Output is correct |
23 |
Correct |
720 ms |
123256 KB |
Output is correct |
24 |
Correct |
51 ms |
28152 KB |
Output is correct |
25 |
Incorrect |
28 ms |
25080 KB |
Output isn't correct |
26 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
434 ms |
68460 KB |
Output is correct |
2 |
Correct |
1280 ms |
99960 KB |
Output is correct |
3 |
Correct |
316 ms |
49212 KB |
Output is correct |
4 |
Correct |
689 ms |
75060 KB |
Output is correct |
5 |
Correct |
1466 ms |
95176 KB |
Output is correct |
6 |
Correct |
153 ms |
46588 KB |
Output is correct |
7 |
Correct |
349 ms |
88268 KB |
Output is correct |
8 |
Correct |
405 ms |
97016 KB |
Output is correct |
9 |
Correct |
27 ms |
27640 KB |
Output is correct |
10 |
Correct |
164 ms |
46460 KB |
Output is correct |
11 |
Correct |
386 ms |
92872 KB |
Output is correct |
12 |
Correct |
338 ms |
69240 KB |
Output is correct |
13 |
Correct |
2369 ms |
26380 KB |
Output is correct |
14 |
Correct |
271 ms |
43004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
434 ms |
68460 KB |
Output is correct |
2 |
Correct |
1280 ms |
99960 KB |
Output is correct |
3 |
Correct |
316 ms |
49212 KB |
Output is correct |
4 |
Correct |
689 ms |
75060 KB |
Output is correct |
5 |
Correct |
1466 ms |
95176 KB |
Output is correct |
6 |
Correct |
153 ms |
46588 KB |
Output is correct |
7 |
Correct |
349 ms |
88268 KB |
Output is correct |
8 |
Correct |
405 ms |
97016 KB |
Output is correct |
9 |
Correct |
27 ms |
27640 KB |
Output is correct |
10 |
Correct |
164 ms |
46460 KB |
Output is correct |
11 |
Correct |
386 ms |
92872 KB |
Output is correct |
12 |
Correct |
338 ms |
69240 KB |
Output is correct |
13 |
Correct |
2369 ms |
26380 KB |
Output is correct |
14 |
Correct |
271 ms |
43004 KB |
Output is correct |
15 |
Correct |
773 ms |
67144 KB |
Output is correct |
16 |
Correct |
802 ms |
61908 KB |
Output is correct |
17 |
Correct |
886 ms |
72040 KB |
Output is correct |
18 |
Correct |
1106 ms |
78920 KB |
Output is correct |
19 |
Correct |
296 ms |
49640 KB |
Output is correct |
20 |
Correct |
1283 ms |
83192 KB |
Output is correct |
21 |
Correct |
1174 ms |
102776 KB |
Output is correct |
22 |
Correct |
824 ms |
76536 KB |
Output is correct |
23 |
Correct |
815 ms |
87648 KB |
Output is correct |
24 |
Correct |
565 ms |
56660 KB |
Output is correct |
25 |
Correct |
1309 ms |
84340 KB |
Output is correct |
26 |
Correct |
1205 ms |
81888 KB |
Output is correct |
27 |
Correct |
1152 ms |
78840 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 |
22 ms |
23796 KB |
Output is correct |
32 |
Correct |
22 ms |
23800 KB |
Output is correct |
33 |
Correct |
1767 ms |
27676 KB |
Output is correct |
34 |
Correct |
20 ms |
23800 KB |
Output is correct |
35 |
Correct |
21 ms |
23800 KB |
Output is correct |
36 |
Correct |
25 ms |
23928 KB |
Output is correct |
37 |
Correct |
25 ms |
23928 KB |
Output is correct |
38 |
Correct |
1478 ms |
25976 KB |
Output is correct |
39 |
Correct |
834 ms |
25336 KB |
Output is correct |
40 |
Correct |
1469 ms |
25916 KB |
Output is correct |
41 |
Correct |
21 ms |
23800 KB |
Output is correct |
42 |
Correct |
20 ms |
23800 KB |
Output is correct |
43 |
Correct |
21 ms |
23800 KB |
Output is correct |
44 |
Correct |
22 ms |
23800 KB |
Output is correct |
45 |
Correct |
253 ms |
24696 KB |
Output is correct |
46 |
Correct |
2089 ms |
26532 KB |
Output is correct |
47 |
Correct |
1494 ms |
25976 KB |
Output is correct |
48 |
Correct |
21 ms |
23800 KB |
Output is correct |
49 |
Correct |
2170 ms |
127852 KB |
Output is correct |
50 |
Correct |
720 ms |
123256 KB |
Output is correct |
51 |
Correct |
51 ms |
28152 KB |
Output is correct |
52 |
Incorrect |
28 ms |
25080 KB |
Output isn't correct |
53 |
Halted |
0 ms |
0 KB |
- |