Submission #362489

#	Time	Username	Problem	Language	Result	Execution time	Memory
362489		_martynas	Cheap flights (LMIO18_pigus_skrydziai)	C++11	100 / 100	1620 ms	89304 KiB

pigus_skrydziai

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;
const int MAX_N = 3e5+5;
const int MAX_M = 5e5+5;
#define PB push_back
#define F first
#define S second

int n, m;
vector<pii> Adj[MAX_N];
map<pii, int> M;
ll Star[MAX_N];
pii MaxWeight[MAX_N][2];

int main()
{
    //freopen("lmio_2018_3e2_menesinis_bilietas_vyr.in", "r", stdin);
    //freopen("lmio_2018_3e2_menesinis_bilietas_vyr.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for(int i = 0; i < m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        a--;
        b--;
        Adj[a].PB({b, w});
        Adj[b].PB({a, w});
        Star[a] += w;
        Star[b] += w;
        M[{a, b}] = w;
        M[{b, a}] = w;
    }

    ll ans = 0;

    for(int i = 0; i < n; i++)
    {
        ans = max(ans, Star[i]);
        MaxWeight[i][0] = MaxWeight[i][1] = {-1, 0};
        for(pii e : Adj[i])
        {
            if(MaxWeight[i][0].S < e.S)
            {
                MaxWeight[i][0] = e;
                if(MaxWeight[i][0].S > MaxWeight[i][1].S)
                    swap(MaxWeight[i][0], MaxWeight[i][1]);
            }
        }

        if(MaxWeight[i][0].F != -1)
        {
            auto it = M.find({MaxWeight[i][0].F, MaxWeight[i][1].F});
            if(it != M.end())
                ans = max(ans, (ll)MaxWeight[i][0].S + MaxWeight[i][1].S + it->second);
        }
    }

    printf("%lld", ans);

    return 0;
}

Compilation message (stderr)

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
pigus_skrydziai.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |         scanf("%d%d%d", &a, &b, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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