Submission #498268

#	Time	Username	Problem	Language	Result	Execution time	Memory
498268		Kipras	Cheap flights (LMIO18_pigus_skrydziai)	C++14	37 / 100	3057 ms	37712 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 < (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 / 12
• Subtask 2: 25 / 25
• Subtask 3: 0 / 16
• Subtask 4: 0 / 47