Submission #1098952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098952		AliHasanli	Cheap flights (LMIO18_pigus_skrydziai)	C++17	37 / 100	3078 ms	45880 KiB

pigus_skrydziai

#include <bits/stdc++.h>
using namespace std;
long long selected[300001];
vector<pair<pair<int,int>,long long> >edges;
vector<pair<int,long long> >g[300001];
int main()
{
    int n,m;
    long long ans=0;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        long long p;
        cin>>a>>b>>p;
        edges.push_back({{a,b},p});
        g[a].push_back({b,p});
        g[b].push_back({a,p});
    }
    for(int i=1;i<=n;i++)
    {
        long long sum=0;
        for(pair<int,long long>go:g[i])sum+=go.second;
        ans=max(ans,sum);
    }
    for(pair<pair<int,int>,long long>edge:edges)
    {
        long long sum=edge.second;
        for(pair<int,long long>go:g[edge.first.first])selected[go.first]=go.second;
        for(pair<int,long long>go:g[edge.first.second])if(selected[go.first]>0)sum=max(sum,edge.second+go.second+selected[go.first]);
        for(pair<int,long long>go:g[edge.first.first])selected[go.first]=0;
        ans=max(ans,sum);
    }
    cout<<ans;
    return 0;
}

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