#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll maxN = 1e5*3+1;
ll n, m;
vector<pair<ll, ll>> adj[maxN];
vector<pair<ll, ll>> adjFast[maxN];
ll findVal(ll v, ll v1){
ll l = 0, h = adjFast[v1].size()-1;
while(l<h){
ll mid = l+((h-l)/2);
if(adjFast[v1][mid].first==v)return adjFast[v1][mid].second;
else if(adjFast[v1][mid].first<v)l=mid+1;
else h=mid-1;
}
return -1;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(nullptr);
cin>>n>>m;
for(ll i = 0; i < m; i++){
ll a, b, c;
cin>>a>>b>>c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
adjFast[a].push_back({b, c});
adjFast[b].push_back({a, c});
}
for(ll i = 1; i <= n; i++)sort(adjFast[i].begin(), adjFast[i].end());
ll ans=0;
for(ll i = 1; i <= n; i++){
ll temp=0;
for(auto x : adj[i]){
temp+=x.second;
}
ans=max(ans, temp);
}
for(ll i = 1; i <= n; i++){
for(ll x = 0; x < (ll)(adj[i].size())-1; x++){
ll temp=0;
ll val=-1;
ll v1=adj[i][x].first, v2=adj[i][x+1].first;
val = findVal(v2, v1);
if(val==-1)continue;
temp=adj[i][x].second+adj[i][x+1].second+val;
ans=max(ans, temp);
}
}
cout<<ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
14380 KB |
Output is correct |
2 |
Correct |
7 ms |
14284 KB |
Output is correct |
3 |
Correct |
7 ms |
14284 KB |
Output is correct |
4 |
Correct |
7 ms |
14384 KB |
Output is correct |
5 |
Correct |
7 ms |
14380 KB |
Output is correct |
6 |
Correct |
13 ms |
16196 KB |
Output is correct |
7 |
Correct |
7 ms |
14404 KB |
Output is correct |
8 |
Correct |
7 ms |
14284 KB |
Output is correct |
9 |
Correct |
8 ms |
14412 KB |
Output is correct |
10 |
Correct |
7 ms |
14412 KB |
Output is correct |
11 |
Correct |
8 ms |
14412 KB |
Output is correct |
12 |
Correct |
7 ms |
14400 KB |
Output is correct |
13 |
Correct |
7 ms |
14404 KB |
Output is correct |
14 |
Correct |
7 ms |
14408 KB |
Output is correct |
15 |
Correct |
7 ms |
14396 KB |
Output is correct |
16 |
Correct |
7 ms |
14404 KB |
Output is correct |
17 |
Correct |
7 ms |
14284 KB |
Output is correct |
18 |
Correct |
7 ms |
14412 KB |
Output is correct |
19 |
Correct |
8 ms |
14628 KB |
Output is correct |
20 |
Correct |
8 ms |
14412 KB |
Output is correct |
21 |
Correct |
7 ms |
14408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
14380 KB |
Output is correct |
2 |
Correct |
7 ms |
14284 KB |
Output is correct |
3 |
Correct |
7 ms |
14284 KB |
Output is correct |
4 |
Correct |
7 ms |
14384 KB |
Output is correct |
5 |
Correct |
7 ms |
14380 KB |
Output is correct |
6 |
Correct |
13 ms |
16196 KB |
Output is correct |
7 |
Correct |
7 ms |
14404 KB |
Output is correct |
8 |
Correct |
7 ms |
14284 KB |
Output is correct |
9 |
Correct |
8 ms |
14412 KB |
Output is correct |
10 |
Correct |
7 ms |
14412 KB |
Output is correct |
11 |
Correct |
8 ms |
14412 KB |
Output is correct |
12 |
Correct |
7 ms |
14400 KB |
Output is correct |
13 |
Correct |
7 ms |
14404 KB |
Output is correct |
14 |
Correct |
7 ms |
14408 KB |
Output is correct |
15 |
Correct |
7 ms |
14396 KB |
Output is correct |
16 |
Correct |
7 ms |
14404 KB |
Output is correct |
17 |
Correct |
7 ms |
14284 KB |
Output is correct |
18 |
Correct |
7 ms |
14412 KB |
Output is correct |
19 |
Correct |
8 ms |
14628 KB |
Output is correct |
20 |
Correct |
8 ms |
14412 KB |
Output is correct |
21 |
Correct |
7 ms |
14408 KB |
Output is correct |
22 |
Correct |
374 ms |
60832 KB |
Output is correct |
23 |
Correct |
203 ms |
49712 KB |
Output is correct |
24 |
Correct |
17 ms |
16712 KB |
Output is correct |
25 |
Correct |
10 ms |
14992 KB |
Output is correct |
26 |
Correct |
10 ms |
15048 KB |
Output is correct |
27 |
Correct |
9 ms |
14672 KB |
Output is correct |
28 |
Correct |
96 ms |
34664 KB |
Output is correct |
29 |
Correct |
47 ms |
22784 KB |
Output is correct |
30 |
Correct |
73 ms |
25232 KB |
Output is correct |
31 |
Correct |
8 ms |
14400 KB |
Output is correct |
32 |
Correct |
8 ms |
14364 KB |
Output is correct |
33 |
Correct |
194 ms |
57792 KB |
Output is correct |
34 |
Correct |
153 ms |
55236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
124 ms |
35528 KB |
Output is correct |
2 |
Correct |
316 ms |
47508 KB |
Output is correct |
3 |
Correct |
92 ms |
25924 KB |
Output is correct |
4 |
Correct |
188 ms |
37188 KB |
Output is correct |
5 |
Correct |
386 ms |
48332 KB |
Output is correct |
6 |
Correct |
44 ms |
23628 KB |
Output is correct |
7 |
Correct |
108 ms |
41284 KB |
Output is correct |
8 |
Correct |
131 ms |
45348 KB |
Output is correct |
9 |
Correct |
9 ms |
14428 KB |
Output is correct |
10 |
Correct |
43 ms |
23756 KB |
Output is correct |
11 |
Correct |
117 ms |
44816 KB |
Output is correct |
12 |
Correct |
78 ms |
32952 KB |
Output is correct |
13 |
Correct |
8 ms |
14284 KB |
Output is correct |
14 |
Correct |
56 ms |
24264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
124 ms |
35528 KB |
Output is correct |
2 |
Correct |
316 ms |
47508 KB |
Output is correct |
3 |
Correct |
92 ms |
25924 KB |
Output is correct |
4 |
Correct |
188 ms |
37188 KB |
Output is correct |
5 |
Correct |
386 ms |
48332 KB |
Output is correct |
6 |
Correct |
44 ms |
23628 KB |
Output is correct |
7 |
Correct |
108 ms |
41284 KB |
Output is correct |
8 |
Correct |
131 ms |
45348 KB |
Output is correct |
9 |
Correct |
9 ms |
14428 KB |
Output is correct |
10 |
Correct |
43 ms |
23756 KB |
Output is correct |
11 |
Correct |
117 ms |
44816 KB |
Output is correct |
12 |
Correct |
78 ms |
32952 KB |
Output is correct |
13 |
Correct |
8 ms |
14284 KB |
Output is correct |
14 |
Correct |
56 ms |
24264 KB |
Output is correct |
15 |
Correct |
10 ms |
14380 KB |
Output is correct |
16 |
Correct |
7 ms |
14284 KB |
Output is correct |
17 |
Correct |
7 ms |
14284 KB |
Output is correct |
18 |
Correct |
7 ms |
14384 KB |
Output is correct |
19 |
Correct |
7 ms |
14380 KB |
Output is correct |
20 |
Correct |
13 ms |
16196 KB |
Output is correct |
21 |
Correct |
7 ms |
14404 KB |
Output is correct |
22 |
Correct |
7 ms |
14284 KB |
Output is correct |
23 |
Correct |
8 ms |
14412 KB |
Output is correct |
24 |
Correct |
7 ms |
14412 KB |
Output is correct |
25 |
Correct |
8 ms |
14412 KB |
Output is correct |
26 |
Correct |
7 ms |
14400 KB |
Output is correct |
27 |
Correct |
7 ms |
14404 KB |
Output is correct |
28 |
Correct |
7 ms |
14408 KB |
Output is correct |
29 |
Correct |
7 ms |
14396 KB |
Output is correct |
30 |
Correct |
7 ms |
14404 KB |
Output is correct |
31 |
Correct |
7 ms |
14284 KB |
Output is correct |
32 |
Correct |
7 ms |
14412 KB |
Output is correct |
33 |
Correct |
8 ms |
14628 KB |
Output is correct |
34 |
Correct |
8 ms |
14412 KB |
Output is correct |
35 |
Correct |
7 ms |
14408 KB |
Output is correct |
36 |
Correct |
374 ms |
60832 KB |
Output is correct |
37 |
Correct |
203 ms |
49712 KB |
Output is correct |
38 |
Correct |
17 ms |
16712 KB |
Output is correct |
39 |
Correct |
10 ms |
14992 KB |
Output is correct |
40 |
Correct |
10 ms |
15048 KB |
Output is correct |
41 |
Correct |
9 ms |
14672 KB |
Output is correct |
42 |
Correct |
96 ms |
34664 KB |
Output is correct |
43 |
Correct |
47 ms |
22784 KB |
Output is correct |
44 |
Correct |
73 ms |
25232 KB |
Output is correct |
45 |
Correct |
8 ms |
14400 KB |
Output is correct |
46 |
Correct |
8 ms |
14364 KB |
Output is correct |
47 |
Correct |
194 ms |
57792 KB |
Output is correct |
48 |
Correct |
153 ms |
55236 KB |
Output is correct |
49 |
Correct |
159 ms |
35184 KB |
Output is correct |
50 |
Correct |
111 ms |
33352 KB |
Output is correct |
51 |
Correct |
151 ms |
34700 KB |
Output is correct |
52 |
Correct |
188 ms |
37076 KB |
Output is correct |
53 |
Correct |
72 ms |
25636 KB |
Output is correct |
54 |
Correct |
163 ms |
50120 KB |
Output is correct |
55 |
Correct |
357 ms |
47420 KB |
Output is correct |
56 |
Correct |
225 ms |
37544 KB |
Output is correct |
57 |
Correct |
203 ms |
40644 KB |
Output is correct |
58 |
Correct |
99 ms |
28876 KB |
Output is correct |
59 |
Correct |
249 ms |
45628 KB |
Output is correct |
60 |
Correct |
187 ms |
42892 KB |
Output is correct |
61 |
Incorrect |
156 ms |
41212 KB |
Output isn't correct |