Submission #498279

#	Time	Username	Problem	Language	Result	Execution time	Memory
498279		Kipras	Cheap flights (LMIO18_pigus_skrydziai)	C++14	53 / 100	645 ms	57996 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];
vector<pair<ll, ll>> adjFast[maxN];

int findVal(int v, int v1){
    int l = 0, h = adjFast[v1].size();
    while(l<h){
        int 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(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});
        adjFast[a].push_back({b, c});
        adjFast[b].push_back({a, c});
    }

    for(int i = 1; i <= n; i++)sort(adjFast[i].begin(), adjFast[i].end());

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

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