oj.uz

Submission #498268

# Submission time Handle Problem Language Result Execution time Memory
498268 2021-12-24T18:05:03 Z Kipras Cheap flights (LMIO18_pigus_skrydziai) C++14
37 / 100
 3000 ms 37712 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

const int maxN = 1e5*3+1;

ll n, m;
vector<pair<ll, ll>> adj[maxN];

int main()
{

    //ios_base::sync_with_stdio(0);cin.tie(nullptr);

    cin>>n>>m;
    for(int 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});
    }

    ll ans=0;

    for(int i = 1; i <= n; i++){
        ll temp=0;
        for(auto x : adj[i]){
            temp+=x.second;
        }
        ans=max(ans, temp);
    }

    for(int i = 1; i <= n; i++){
        for(int x = 0; x < (int)(adj[i].size())-1; x++){
            ll temp=0;
            ll val=-1;
            ll v1=adj[i][x].first, v2=adj[i][x+1].first;
            if(adj[v1].size()<adj[v2].size()){
                for(auto z : adj[v1]){
                    if(z.first==v2){
                        val=z.second;
                        break;
                    }
                }
            }else{
                for(auto z : adj[v2]){
                    if(z.first==v1){
                        val=z.second;
                        break;
                    }
                }
            }
            if(val==-1)continue;
            temp=adj[i][x].second+adj[i][x+1].second+val;
            ans=max(ans, temp);
        }
    }

    cout<<ans;

    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 4 ms 7288 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 19 ms 8268 KB Output is correct
7 Correct 4 ms 7244 KB Output is correct
8 Correct 4 ms 7336 KB Output is correct
9 Correct 4 ms 7244 KB Output is correct
10 Correct 4 ms 7244 KB Output is correct
11 Correct 4 ms 7340 KB Output is correct
12 Correct 4 ms 7244 KB Output is correct
13 Correct 4 ms 7340 KB Output is correct
14 Correct 5 ms 7372 KB Output is correct
15 Correct 4 ms 7244 KB Output is correct
16 Correct 4 ms 7344 KB Output is correct
17 Correct 6 ms 7244 KB Output is correct
18 Correct 5 ms 7356 KB Output is correct
19 Correct 5 ms 7372 KB Output is correct
20 Correct 4 ms 7352 KB Output is correct
21 Correct 4 ms 7244 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7244 KB Output is correct
3 Correct 4 ms 7288 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 19 ms 8268 KB Output is correct
7 Correct 4 ms 7244 KB Output is correct
8 Correct 4 ms 7336 KB Output is correct
9 Correct 4 ms 7244 KB Output is correct
10 Correct 4 ms 7244 KB Output is correct
11 Correct 4 ms 7340 KB Output is correct
12 Correct 4 ms 7244 KB Output is correct
13 Correct 4 ms 7340 KB Output is correct
14 Correct 5 ms 7372 KB Output is correct
15 Correct 4 ms 7244 KB Output is correct
16 Correct 4 ms 7344 KB Output is correct
17 Correct 6 ms 7244 KB Output is correct
18 Correct 5 ms 7356 KB Output is correct
19 Correct 5 ms 7372 KB Output is correct
20 Correct 4 ms 7352 KB Output is correct
21 Correct 4 ms 7244 KB Output is correct
22 Correct 686 ms 37712 KB Output is correct
23 Correct 1149 ms 32208 KB Output is correct
24 Correct 22 ms 8644 KB Output is correct
25 Correct 9 ms 7632 KB Output is correct
26 Correct 11 ms 7740 KB Output is correct
27 Correct 9 ms 7444 KB Output is correct
28 Correct 273 ms 19544 KB Output is correct
29 Correct 84 ms 12128 KB Output is correct
30 Correct 185 ms 13868 KB Output is correct
31 Correct 5 ms 7376 KB Output is correct
32 Correct 5 ms 7392 KB Output is correct
33 Correct 2681 ms 35560 KB Output is correct
34 Correct 2075 ms 31512 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 16852 KB Output is correct
2 Correct 332 ms 22992 KB Output is correct
3 Correct 90 ms 12596 KB Output is correct
4 Correct 207 ms 17592 KB Output is correct
5 Correct 385 ms 22852 KB Output is correct
6 Correct 104 ms 12612 KB Output is correct
7 Correct 206 ms 23184 KB Output is correct
8 Correct 228 ms 25788 KB Output is correct
9 Correct 6 ms 7376 KB Output is correct
10 Correct 115 ms 12668 KB Output is correct
11 Execution timed out 3057 ms 24408 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 16852 KB Output is correct
2 Correct 332 ms 22992 KB Output is correct
3 Correct 90 ms 12596 KB Output is correct
4 Correct 207 ms 17592 KB Output is correct
5 Correct 385 ms 22852 KB Output is correct
6 Correct 104 ms 12612 KB Output is correct
7 Correct 206 ms 23184 KB Output is correct
8 Correct 228 ms 25788 KB Output is correct
9 Correct 6 ms 7376 KB Output is correct
10 Correct 115 ms 12668 KB Output is correct
11 Execution timed out 3057 ms 24408 KB Time limit exceeded
12 Halted 0 ms 0 KB -