Submission #1169438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169438		vladprog	Cheap flights (LMIO18_pigus_skrydziai)	C++20	100 / 100	205 ms	76444 KiB

pigus_skrydziai

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back

const int N=14e5+100;

vector<pii> g[N];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

    unordered_map<ll,int> e;
    e.reserve(7e5);
    auto set=[&](int a,int b)->int&
    {
        if(a>b)
            swap(a,b);
        return e[(a<<25)|b];
    };
    auto get=[&](int a,int b)->int
    {
        if(a>b)
            swap(a,b);
        auto it=e.find((a<<25)|b);
        return it==e.end()?0:it->se;
    };

    int t=1;
    while(t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            g[i].clear();
        e.clear();
        while(m--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            assert(get(a,b)==0);
            set(a,b)+=c;
        }
        for(auto[ab,c]:e)
        {
            int a=ab>>25;
            int b=ab&((1<<25)-1);
            g[a].pb({c,b});
            g[b].pb({c,a});
        }
        int ans=0;
        for(int v=1;v<=n;v++)
        {
            int sum=0;
            for(auto[cnt,_]:g[v])
                sum+=cnt;
            ans=max(ans,sum);
            if(sz(g[v])>=2)
            {
                sort(all(g[v]),greater<>());
                ans=max(ans,g[v][0].fi+g[v][1].fi+get(g[v][0].se,g[v][1].se));
            }
        }
        cout<<ans<<"\n";
    }
}

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