제출 #1139360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139360		teo_55	Cheap flights (LMIO18_pigus_skrydziai)	C++20	12 / 100	3095 ms	46404 KiB

pigus_skrydziai

#include<iostream>
#include<vector>
#include<set>
#include<map>
#define ll long long
const int NMAX=500005;
std::vector<ll>v(NMAX);
std::map<std::pair<int, int>, std::pair<bool, ll>>mp;
ll ans=0;
int n, m;
int main()
{
    bool task3=true;
    std::cin>>n>>m;
    for(int i=0; i<m; ++i)
    {
        int from, to, cost;
        std::cin>>from>>to>>cost;
        if(cost!=1)
            task3=false;
        v[from]+=cost;
        v[to]+=cost;
        if(to<from)
            std::swap(to, from);
        mp[{from, to}]={true, cost};
    }
    for(int i=1; i<=n; ++i)
        ans=std::max(ans, v[i]);
    if(task3)
    {
        if(ans>=3)
        {
            std::cout<<ans;
            return 0;
        }
        for(int i=1; i<=n-2; ++i)
            for(int j=i+1; j<=n-1; ++j)
                for(int k=j+1; k<=n; ++k)
                    if(mp[{i, j}].first && mp[{i, k}].first && mp[{j, k}].first)
                    {
                        std::cout<<3;
                        return 0;
                    }
    }
    for(int i=1; i<=n-2; ++i)
        for(int j=i+1; j<=n-1; ++j)
            for(int k=j+1; k<=n; ++k)
                if(mp[{i, j}].first && mp[{i, k}].first && mp[{j, k}].first)
                    ans=std::max(ans, mp[{i, j}].second+mp[{i, k}].second+mp[{j, k}].second);
    std::cout<<ans;
    return 0;
}

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