oj.uz

Submission #198167

# Submission time Handle Problem Language Result Execution time Memory
198167 2020-01-25T01:59:16 Z model_code Cheap flights (LMIO18_pigus_skrydziai) C++14
100 / 100
 1586 ms 63060 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 21 ms 2808 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 4 ms 504 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 21 ms 2808 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 4 ms 504 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 256 KB Output is correct
22 Correct 1586 ms 63056 KB Output is correct
23 Correct 649 ms 63060 KB Output is correct
24 Correct 29 ms 2812 KB Output is correct
25 Correct 9 ms 1016 KB Output is correct
26 Correct 8 ms 1016 KB Output is correct
27 Correct 5 ms 632 KB Output is correct
28 Correct 526 ms 25360 KB Output is correct
29 Correct 161 ms 10400 KB Output is correct
30 Correct 289 ms 15992 KB Output is correct
31 Correct 3 ms 376 KB Output is correct
32 Correct 2 ms 504 KB Output is correct
33 Correct 876 ms 62072 KB Output is correct
34 Correct 761 ms 56952 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 31040 KB Output is correct
2 Correct 772 ms 49880 KB Output is correct
3 Correct 204 ms 16760 KB Output is correct
4 Correct 427 ms 32632 KB Output is correct
5 Correct 1025 ms 45816 KB Output is correct
6 Correct 132 ms 16060 KB Output is correct
7 Correct 336 ms 42644 KB Output is correct
8 Correct 311 ms 49660 KB Output is correct
9 Correct 14 ms 12280 KB Output is correct
10 Correct 134 ms 15992 KB Output is correct
11 Correct 441 ms 43760 KB Output is correct
12 Correct 399 ms 31740 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 208 ms 12924 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 31040 KB Output is correct
2 Correct 772 ms 49880 KB Output is correct
3 Correct 204 ms 16760 KB Output is correct
4 Correct 427 ms 32632 KB Output is correct
5 Correct 1025 ms 45816 KB Output is correct
6 Correct 132 ms 16060 KB Output is correct
7 Correct 336 ms 42644 KB Output is correct
8 Correct 311 ms 49660 KB Output is correct
9 Correct 14 ms 12280 KB Output is correct
10 Correct 134 ms 15992 KB Output is correct
11 Correct 441 ms 43760 KB Output is correct
12 Correct 399 ms 31740 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 208 ms 12924 KB Output is correct
15 Correct 553 ms 28176 KB Output is correct
16 Correct 642 ms 25336 KB Output is correct
17 Correct 597 ms 32432 KB Output is correct
18 Correct 822 ms 37644 KB Output is correct
19 Correct 285 ms 18604 KB Output is correct
20 Correct 817 ms 38076 KB Output is correct
21 Correct 740 ms 49936 KB Output is correct
22 Correct 464 ms 33276 KB Output is correct
23 Correct 659 ms 41560 KB Output is correct
24 Correct 364 ms 21236 KB Output is correct
25 Correct 940 ms 38756 KB Output is correct
26 Correct 787 ms 37804 KB Output is correct
27 Correct 927 ms 37184 KB Output is correct
28 Correct 2 ms 376 KB Output is correct
29 Correct 1 ms 376 KB Output is correct
30 Correct 2 ms 256 KB Output is correct
31 Correct 2 ms 256 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 21 ms 2808 KB Output is correct
34 Correct 2 ms 380 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 376 KB Output is correct
37 Correct 2 ms 376 KB Output is correct
38 Correct 3 ms 376 KB Output is correct
39 Correct 2 ms 376 KB Output is correct
40 Correct 2 ms 376 KB Output is correct
41 Correct 2 ms 376 KB Output is correct
42 Correct 2 ms 376 KB Output is correct
43 Correct 2 ms 376 KB Output is correct
44 Correct 2 ms 256 KB Output is correct
45 Correct 3 ms 376 KB Output is correct
46 Correct 4 ms 504 KB Output is correct
47 Correct 2 ms 376 KB Output is correct
48 Correct 2 ms 256 KB Output is correct
49 Correct 1586 ms 63056 KB Output is correct
50 Correct 649 ms 63060 KB Output is correct
51 Correct 29 ms 2812 KB Output is correct
52 Correct 9 ms 1016 KB Output is correct
53 Correct 8 ms 1016 KB Output is correct
54 Correct 5 ms 632 KB Output is correct
55 Correct 526 ms 25360 KB Output is correct
56 Correct 161 ms 10400 KB Output is correct
57 Correct 289 ms 15992 KB Output is correct
58 Correct 3 ms 376 KB Output is correct
59 Correct 2 ms 504 KB Output is correct
60 Correct 876 ms 62072 KB Output is correct
61 Correct 761 ms 56952 KB Output is correct