oj.uz

Submission #499117

# Submission time Handle Problem Language Result Execution time Memory
499117 2021-12-27T08:53:15 Z Kipras Cheap flights (LMIO18_pigus_skrydziai) C++14
100 / 100
 2138 ms 85196 KB 
#include <bits/stdc++.h>
 
typedef long long ll;
using namespace std;
 
const ll maxN = (1e5*5)+10;
 
ll n, m;
vector<ll> adj[maxN];
map<pair<ll, ll>, ll> adjFast;
 
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);
        adj[b].push_back(a);
        adjFast[{a, b}]=c;
        adjFast[{b, a}]=c;
    }
 
    ll ans=0;
 
    for(ll i = 1; i <= n; i++){
        ll temp=0;
        for(auto x : adj[i]){
            temp+=adjFast[{i, x}];
        }
        for(ll x = 0; x < (ll)(adj[i].size())-1; x++){
            ll v1=adj[i][x], v2=adj[i][x+1];
            if(adjFast.count({v1, v2})){
                temp=max(temp, adjFast[{i, v1}]+adjFast[{i, v2}]+adjFast[{v1, v2}]);
            }
        }
 
        ans=max(ans, temp);
    }
 
    cout<<ans;
 
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 5 ms 11980 KB Output is correct
3 Correct 6 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 31 ms 14924 KB Output is correct
7 Correct 6 ms 11980 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 6 ms 12016 KB Output is correct
10 Correct 8 ms 11980 KB Output is correct
11 Correct 6 ms 12108 KB Output is correct
12 Correct 6 ms 12108 KB Output is correct
13 Correct 6 ms 12080 KB Output is correct
14 Correct 7 ms 11980 KB Output is correct
15 Correct 6 ms 11980 KB Output is correct
16 Correct 6 ms 12052 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Correct 8 ms 12112 KB Output is correct
19 Correct 8 ms 12364 KB Output is correct
20 Correct 6 ms 12040 KB Output is correct
21 Correct 6 ms 11980 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 5 ms 11980 KB Output is correct
3 Correct 6 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 31 ms 14924 KB Output is correct
7 Correct 6 ms 11980 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 6 ms 12016 KB Output is correct
10 Correct 8 ms 11980 KB Output is correct
11 Correct 6 ms 12108 KB Output is correct
12 Correct 6 ms 12108 KB Output is correct
13 Correct 6 ms 12080 KB Output is correct
14 Correct 7 ms 11980 KB Output is correct
15 Correct 6 ms 11980 KB Output is correct
16 Correct 6 ms 12052 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Correct 8 ms 12112 KB Output is correct
19 Correct 8 ms 12364 KB Output is correct
20 Correct 6 ms 12040 KB Output is correct
21 Correct 6 ms 11980 KB Output is correct
22 Correct 2138 ms 85196 KB Output is correct
23 Correct 1020 ms 82756 KB Output is correct
24 Correct 34 ms 14984 KB Output is correct
25 Correct 16 ms 12996 KB Output is correct
26 Correct 15 ms 12876 KB Output is correct
27 Correct 8 ms 12492 KB Output is correct
28 Correct 573 ms 41112 KB Output is correct
29 Correct 250 ms 23876 KB Output is correct
30 Correct 448 ms 29736 KB Output is correct
31 Correct 7 ms 12108 KB Output is correct
32 Correct 6 ms 12084 KB Output is correct
33 Correct 755 ms 83632 KB Output is correct
34 Correct 637 ms 78000 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 40112 KB Output is correct
2 Correct 618 ms 59152 KB Output is correct
3 Correct 162 ms 27652 KB Output is correct
4 Correct 377 ms 42696 KB Output is correct
5 Correct 1112 ms 59580 KB Output is correct
6 Correct 224 ms 29752 KB Output is correct
7 Correct 295 ms 52236 KB Output is correct
8 Correct 386 ms 59000 KB Output is correct
9 Correct 8 ms 12208 KB Output is correct
10 Correct 222 ms 29880 KB Output is correct
11 Correct 360 ms 56676 KB Output is correct
12 Correct 343 ms 47392 KB Output is correct
13 Correct 6 ms 11980 KB Output is correct
14 Correct 251 ms 26716 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 40112 KB Output is correct
2 Correct 618 ms 59152 KB Output is correct
3 Correct 162 ms 27652 KB Output is correct
4 Correct 377 ms 42696 KB Output is correct
5 Correct 1112 ms 59580 KB Output is correct
6 Correct 224 ms 29752 KB Output is correct
7 Correct 295 ms 52236 KB Output is correct
8 Correct 386 ms 59000 KB Output is correct
9 Correct 8 ms 12208 KB Output is correct
10 Correct 222 ms 29880 KB Output is correct
11 Correct 360 ms 56676 KB Output is correct
12 Correct 343 ms 47392 KB Output is correct
13 Correct 6 ms 11980 KB Output is correct
14 Correct 251 ms 26716 KB Output is correct
15 Correct 6 ms 11980 KB Output is correct
16 Correct 5 ms 11980 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Correct 6 ms 11980 KB Output is correct
19 Correct 6 ms 11980 KB Output is correct
20 Correct 31 ms 14924 KB Output is correct
21 Correct 6 ms 11980 KB Output is correct
22 Correct 6 ms 11980 KB Output is correct
23 Correct 6 ms 12016 KB Output is correct
24 Correct 8 ms 11980 KB Output is correct
25 Correct 6 ms 12108 KB Output is correct
26 Correct 6 ms 12108 KB Output is correct
27 Correct 6 ms 12080 KB Output is correct
28 Correct 7 ms 11980 KB Output is correct
29 Correct 6 ms 11980 KB Output is correct
30 Correct 6 ms 12052 KB Output is correct
31 Correct 6 ms 11980 KB Output is correct
32 Correct 8 ms 12112 KB Output is correct
33 Correct 8 ms 12364 KB Output is correct
34 Correct 6 ms 12040 KB Output is correct
35 Correct 6 ms 11980 KB Output is correct
36 Correct 2138 ms 85196 KB Output is correct
37 Correct 1020 ms 82756 KB Output is correct
38 Correct 34 ms 14984 KB Output is correct
39 Correct 16 ms 12996 KB Output is correct
40 Correct 15 ms 12876 KB Output is correct
41 Correct 8 ms 12492 KB Output is correct
42 Correct 573 ms 41112 KB Output is correct
43 Correct 250 ms 23876 KB Output is correct
44 Correct 448 ms 29736 KB Output is correct
45 Correct 7 ms 12108 KB Output is correct
46 Correct 6 ms 12084 KB Output is correct
47 Correct 755 ms 83632 KB Output is correct
48 Correct 637 ms 78000 KB Output is correct
49 Correct 602 ms 43296 KB Output is correct
50 Correct 516 ms 41132 KB Output is correct
51 Correct 805 ms 46284 KB Output is correct
52 Correct 1072 ms 53776 KB Output is correct
53 Correct 243 ms 28280 KB Output is correct
54 Correct 1097 ms 58180 KB Output is correct
55 Correct 618 ms 59032 KB Output is correct
56 Correct 391 ms 43352 KB Output is correct
57 Correct 711 ms 52724 KB Output is correct
58 Correct 409 ms 36988 KB Output is correct
59 Correct 1101 ms 61240 KB Output is correct
60 Correct 1002 ms 59692 KB Output is correct
61 Correct 1092 ms 57780 KB Output is correct