Submission #198167

#	Time	Username	Problem	Language	Result	Execution time	Memory
198167		model_code	Cheap flights (LMIO18_pigus_skrydziai)	C++14	100 / 100	1586 ms	63060 KiB

pigus_skrydziai

#include <cstdio>
#include <cstdint>
#include <utility>
#include <algorithm>
#include <map>

using namespace std;

const int64_t MAX_N = 300000 + 100;

map<pair<int64_t, int64_t>, int64_t> briaunos;
pair<int,int64_t> sunkiausi[MAX_N][2];
int64_t zvaigzde[MAX_N];

void AtnaujintiSunkiausius(int v, int w, int64_t svoris)
{
    if (sunkiausi[v][0].second < svoris) {
        sunkiausi[v][1] = sunkiausi[v][0];
        sunkiausi[v][0] = make_pair(w, svoris);
    }
    else if (sunkiausi[v][1].second < svoris) {
        sunkiausi[v][1] = make_pair(w, svoris);
    }
}

int main()
{
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < N; ++i) {
        sunkiausi[i][0] = make_pair(-1, -1);
        sunkiausi[i][1] = make_pair(-1, -1);
        zvaigzde[i] = 0;
    }

    for (int j = 0; j < M; ++j) {
        int a, b, svoris;
        scanf("%d%d%d", &a, &b, &svoris);
        AtnaujintiSunkiausius(a - 1, b - 1, svoris);
        AtnaujintiSunkiausius(b - 1, a - 1, svoris);
        zvaigzde[a - 1] += (int64_t) svoris;
        zvaigzde[b - 1] += (int64_t) svoris;
		briaunos[make_pair(a - 1, b - 1)] = (int64_t) svoris;
		briaunos[make_pair(b - 1, a - 1)] = (int64_t) svoris;
    }

    int64_t atsakymas = 0;
    for (int i = 0; i < N; ++i) {
        if (zvaigzde[i] > atsakymas)
            atsakymas = zvaigzde[i];
        if (sunkiausi[i][1].first != -1) {
            map<pair<int64_t, int64_t>, int64_t>::iterator it = briaunos.find(make_pair(sunkiausi[i][0].first, sunkiausi[i][1].first));
            if (it != briaunos.end()) {
                int64_t trikampis = sunkiausi[i][0].second + sunkiausi[i][1].second + it->second;
                if (trikampis > atsakymas)
                    atsakymas = trikampis;
            }
        }
    }

    printf("%lld\n", atsakymas);
    return 0;
}

Compilation message (stderr)

pigus_skrydziai.cpp: In function 'int main()':
pigus_skrydziai.cpp:61:31: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int64_t {aka long int}' [-Wformat=]
     printf("%lld\n", atsakymas);
                               ^
pigus_skrydziai.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
pigus_skrydziai.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a, &b, &svoris);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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