Submission #498266

#	Time	Username	Problem	Language	Result	Execution time	Memory
498266		Kipras	Cheap flights (LMIO18_pigus_skrydziai)	C++14	0 / 100	200 ms	46520 KiB

pigus_skrydziai

#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 < 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;
}

Compilation message (stderr)

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int x = 0; x < adj[i].size()-1; x++){
      |                        ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 25
• Subtask 3: 0 / 16
• Subtask 4: 0 / 47