Submission #237061

#	Time	Username	Problem	Language	Result	Execution time	Memory
237061		Aldas25	Cheap flights (LMIO18_pigus_skrydziai)	C++14	100 / 100	1526 ms	99680 KiB

pigus_skrydziai

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;

const int MAXN = 300100;

int n, m;
ll cnt[MAXN];
map<ll, ll> edges;
vector<pair<ll, int>> adj[MAXN];

ll edgeId (int u, int v) {
    return ((ll)u)*((ll)n+5) + ((ll)v);
}

int main()
{
    FAST_IO;

    //ifstream cin ("lmio_2018_3e2_pigus_skrydziai_vyr.in");
    //ofstream cout ("lmio_2018_3e2_pigus_skrydziai_vyr.out");

    cin >> n >> m;
    REP(m) {
        int u, v; cin >> u >> v;
        ll w; cin >> w;
        adj[u].pb({w,v});
        adj[v].pb({w,u});
        cnt[u] += w;
        cnt[v] += w;
        edges[edgeId(u,v)] = w;
        edges[edgeId(v,u)] = w;
    }

    ll ans = 0;
    FOR(i, 1, n) ans = max(ans, cnt[i]);

    FOR(i, 1, n) {
        if ((int)adj[i].size() < 2) continue;
        sort(adj[i].begin(), adj[i].end());
        reverse(adj[i].begin(), adj[i].end());
        ll cur = adj[i][0].f + adj[i][1].f;
        int u = adj[i][0].s, v = adj[i][1].s;
        ans = max(ans, cur + edges[edgeId(u,v)]);
    }

    cout << ans << "\n";

    return 0;
}

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