제출 #1169436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1169436		Ignut	Cheap flights (LMIO18_pigus_skrydziai)	C++20	100 / 100	544 ms	46396 KiB

pigus_skrydziai

//
// Created by Barichek on 14.03.2024 22:06:28
//
 
#include <bits/stdc++.h>
 
#define F first
#define S second
#define MP make_pair
#define PB push_back
 
#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
 
using namespace std;
 
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
 
#ifdef Energy_is_not_over
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
 
template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
 
#else
#define DEBUG while (false)
#define LOG(...)
#endif
 
const int max_n = 7e5+10, inf = 1000111222;
 
vector<pii> reb[2*max_n];
int buf[2*max_n];
 
void solve()
{
    int m, n;
    cin>>m>>n;
    for (int i=0;i<m;i++){
        reb[i].clear();
    }
    for (int i=0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        reb[a].pb(mp(b,c));
        reb[b].pb(mp(a,c));
    }
    ll ans=0;
    for (int i=0;i<m;i++){
        ll sum=0;
        for (auto j:reb[i]){
            sum+=j.sec;
        }
        ans=max(ans,sum);
    }
 
    vector<int> p(m);
    for (int i=0;i<m;i++){
        p[i]=i;
    }
    sort(all(p),[&](const int& lhs,const int& rhs){
        return len(reb[lhs])>len(reb[rhs]);
    });
 
    vector<int> pos_in_p(m);
    for (int i=0;i<m;i++){
        pos_in_p[p[i]]=i;
    }
    for (int i=0;i<m;i++){
        const int u=p[i];
        for (auto j:reb[u]){
            buf[j.fir]=j.sec;
        }
        {
            for (auto j:reb[u]){
                const int v=j.fir;
                if (pos_in_p[v]>pos_in_p[u]){
                    for (auto k:reb[v]){
                        const int w=k.fir;
                        if (pos_in_p[w]>pos_in_p[v] && buf[w]!=0){
                            ans=max(ans,1ll*j.sec+k.sec+buf[w]);
                        }
                    }
                }
            }
        }
        for (auto j:reb[u]){
            buf[j.fir]=0;
        }
    }
    cout<<ans<<"\n";
}
 
int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    // int tests=1;
    // cin>>tests;
    // while (tests--){
    solve();
    // }
 
    return 0;
}

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