oj.uz

Submission #255306

# Submission time Handle Problem Language Result Execution time Memory
255306 2020-07-31T17:15:08 Z model_code Aesthetic (NOI20_aesthetic) C++17
100 / 100
 905 ms 48900 KB 
#include <bits/stdc++.h>
using namespace std;

bool f[300000];
long long r[2][300000];
int A[300000][4], vt[300000], p[300000], q[300000], d[300000], id[300000];
vector<pair<pair<int, int>, int> > adj[300000];
vector<pair<long long, pair<int, int> > > w;
priority_queue<pair<pair<long long, int>, pair<int, int> > > pq;

int frt(int i) {return i == id[i] ? i : id[i] = frt(id[i]);}

void pr(int i, int t, int o, int l, long long v) {
    if (vt[i]) return;
    vt[i] = 1;
    if (!t) {p[i] = o; q[i] = l; d[i] = d[o] + !!i;}
    r[t][i] = v;
    for (int j = 0; j < adj[i].size(); ++j) if (!vt[adj[i][j].first.first]) pq.emplace(make_pair(-v - adj[i][j].first.second, adj[i][j].first.first), make_pair(i, adj[i][j].second));
}

void it(int i, int l, long long v) {
    if (vt[i] > -1) {if (l < vt[i]) w.emplace_back(r[0][i] + v, make_pair(l, vt[i] - 1)); return;}
    vt[i] = l;
    for (int j = 0; j < adj[i].size(); ++j) pq.emplace(make_pair(-v - adj[i][j].first.second, adj[i][j].first.first), make_pair(l + f[adj[i][j].second], 0));
}

int main() {
    //freopen("in.txt", "r", stdin);
    int N, M, a, b, x, i, j;
    long long c, t;
    scanf("%d %d", &N, &M);
    for (i = 0; i < M; ++i) {for (j = 0; j < 3; ++j) scanf("%d", &A[i][j]); adj[--A[i][0]].emplace_back(make_pair(--A[i][1], A[i][2]), i); adj[A[i][1]].emplace_back(make_pair(A[i][0], A[i][2]), i);}
    for (i = M - 2; i > -1; --i) A[i][3] = max(A[i + 1][2], A[i + 1][3]);
    pr(0, 0, 0, -1, 0);
    while (!pq.empty()) x = pq.top().first.second, c = -pq.top().first.first, a = pq.top().second.first, b = pq.top().second.second, pq.pop(), pr(x, 0, a, b, c);
    memset(vt, 0, sizeof(vt));
    pr(N - 1, 1, N - 1, -1, 0);
    while (!pq.empty()) x = pq.top().first.second, c = -pq.top().first.first, a = pq.top().second.first, b = pq.top().second.second, pq.pop(), pr(x, 1, a, b, c);
    for (i = 0; i < N; ++i) {id[i] = p[i]; if (i) f[q[i]] = 1;}
    for (i = N - 1; i; i = p[i]) id[i] = i;
    for (i = 0; i < M; ++i) if (!f[i] && (r[0][A[i][0]] + A[i][2] + r[1][A[i][1]] == r[0][N - 1] || r[0][A[i][1]] + A[i][2] + r[1][A[i][0]] == r[0][N - 1])) {
        a = frt(A[i][0]);
        b = frt(A[i][1]);
        if (d[a] > d[b]) swap(a, b);
        while (a != b) id[b] = p[b], b = frt(b);
    }
    memset(f, 0, sizeof(f));
    for (i = frt(N - 1), x = 0; i; i = frt(p[i]), ++x) f[q[i]] = 1, w.emplace_back(r[0][p[i]] + A[q[i]][2] + A[q[i]][3] + r[1][i], make_pair(x, x));
    memset(vt, -1, sizeof(vt));
    it(N - 1, 0, 0);
    while (!pq.empty()) a = pq.top().first.second, b = pq.top().second.first, c = -pq.top().first.first, pq.pop(), it(a, b, c);
    sort(w.begin(), w.end());
    iota(id, id + x + 1, 0);
    t = r[0][N - 1];
    for (i = 0; i < w.size(); ++i) for (j = frt(w[i].second.first); j <= w[i].second.second; j = frt(j)) t = max(t, w[i].first), id[j] = j + 1;
    printf("%lld", t);
    return 0;
}

Compilation message

Aesthetic.cpp: In function 'void pr(int, int, int, int, long long int)':
Aesthetic.cpp:18:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[i].size(); ++j) if (!vt[adj[i][j].first.first]) pq.emplace(make_pair(-v - adj[i][j].first.second, adj[i][j].first.first), make_pair(i, adj[i][j].second));
                     ~~^~~~~~~~~~~~~~~
Aesthetic.cpp: In function 'void it(int, int, long long int)':
Aesthetic.cpp:24:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[i].size(); ++j) pq.emplace(make_pair(-v - adj[i][j].first.second, adj[i][j].first.first), make_pair(l + f[adj[i][j].second], 0));
                     ~~^~~~~~~~~~~~~~~
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:55:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < w.size(); ++i) for (j = frt(w[i].second.first); j <= w[i].second.second; j = frt(j)) t = max(t, w[i].first), id[j] = j + 1;
                 ~~^~~~~~~~~~
Aesthetic.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
Aesthetic.cpp:32:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < M; ++i) {for (j = 0; j < 3; ++j) scanf("%d", &A[i][j]); adj[--A[i][0]].emplace_back(make_pair(--A[i][1], A[i][2]), i); adj[A[i][1]].emplace_back(make_pair(A[i][0], A[i][2]), i);}
                                                      ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8832 KB Output is correct
2 Correct 7 ms 8832 KB Output is correct
3 Correct 8 ms 8960 KB Output is correct
4 Correct 6 ms 8832 KB Output is correct
5 Correct 6 ms 8832 KB Output is correct
6 Correct 6 ms 8832 KB Output is correct
7 Correct 7 ms 8832 KB Output is correct
8 Correct 6 ms 8832 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8832 KB Output is correct
2 Correct 7 ms 8832 KB Output is correct
3 Correct 8 ms 8960 KB Output is correct
4 Correct 6 ms 8832 KB Output is correct
5 Correct 6 ms 8832 KB Output is correct
6 Correct 6 ms 8832 KB Output is correct
7 Correct 7 ms 8832 KB Output is correct
8 Correct 6 ms 8832 KB Output is correct
9 Correct 8 ms 9088 KB Output is correct
10 Correct 8 ms 9088 KB Output is correct
11 Correct 7 ms 9088 KB Output is correct
12 Correct 8 ms 9088 KB Output is correct
13 Correct 8 ms 9088 KB Output is correct
14 Correct 7 ms 9088 KB Output is correct
15 Correct 8 ms 9088 KB Output is correct
16 Correct 8 ms 9088 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 35148 KB Output is correct
2 Correct 772 ms 35484 KB Output is correct
3 Correct 780 ms 35000 KB Output is correct
4 Correct 798 ms 34936 KB Output is correct
5 Correct 692 ms 35036 KB Output is correct
6 Correct 770 ms 35576 KB Output is correct
7 Correct 765 ms 35576 KB Output is correct
8 Correct 770 ms 35580 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 832 ms 35624 KB Output is correct
2 Correct 752 ms 35192 KB Output is correct
3 Correct 746 ms 35192 KB Output is correct
4 Correct 763 ms 35812 KB Output is correct
5 Correct 716 ms 35304 KB Output is correct
6 Correct 761 ms 35192 KB Output is correct
7 Correct 699 ms 35192 KB Output is correct
8 Correct 817 ms 35480 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 38368 KB Output is correct
2 Correct 359 ms 31624 KB Output is correct
3 Correct 542 ms 29092 KB Output is correct
4 Correct 517 ms 29048 KB Output is correct
5 Correct 497 ms 28920 KB Output is correct
6 Correct 462 ms 29048 KB Output is correct
7 Correct 486 ms 29048 KB Output is correct
8 Correct 468 ms 29048 KB Output is correct
9 Correct 466 ms 29048 KB Output is correct
10 Correct 473 ms 29176 KB Output is correct
11 Correct 476 ms 29176 KB Output is correct
12 Correct 843 ms 38624 KB Output is correct
13 Correct 468 ms 29176 KB Output is correct
14 Correct 261 ms 36588 KB Output is correct
15 Correct 248 ms 37164 KB Output is correct
16 Correct 720 ms 39512 KB Output is correct
17 Correct 754 ms 37896 KB Output is correct
18 Correct 726 ms 39264 KB Output is correct
19 Correct 337 ms 31480 KB Output is correct
20 Correct 353 ms 31608 KB Output is correct
21 Correct 363 ms 31500 KB Output is correct
22 Correct 342 ms 31480 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 38368 KB Output is correct
2 Correct 359 ms 31624 KB Output is correct
3 Correct 542 ms 29092 KB Output is correct
4 Correct 517 ms 29048 KB Output is correct
5 Correct 497 ms 28920 KB Output is correct
6 Correct 462 ms 29048 KB Output is correct
7 Correct 486 ms 29048 KB Output is correct
8 Correct 468 ms 29048 KB Output is correct
9 Correct 466 ms 29048 KB Output is correct
10 Correct 473 ms 29176 KB Output is correct
11 Correct 476 ms 29176 KB Output is correct
12 Correct 843 ms 38624 KB Output is correct
13 Correct 468 ms 29176 KB Output is correct
14 Correct 261 ms 36588 KB Output is correct
15 Correct 248 ms 37164 KB Output is correct
16 Correct 720 ms 39512 KB Output is correct
17 Correct 754 ms 37896 KB Output is correct
18 Correct 726 ms 39264 KB Output is correct
19 Correct 337 ms 31480 KB Output is correct
20 Correct 353 ms 31608 KB Output is correct
21 Correct 363 ms 31500 KB Output is correct
22 Correct 342 ms 31480 KB Output is correct
23 Correct 794 ms 39484 KB Output is correct
24 Correct 421 ms 32492 KB Output is correct
25 Correct 458 ms 29000 KB Output is correct
26 Correct 530 ms 31156 KB Output is correct
27 Correct 489 ms 31068 KB Output is correct
28 Correct 465 ms 29492 KB Output is correct
29 Correct 498 ms 33188 KB Output is correct
30 Correct 478 ms 31052 KB Output is correct
31 Correct 486 ms 31396 KB Output is correct
32 Correct 529 ms 31216 KB Output is correct
33 Correct 514 ms 30256 KB Output is correct
34 Correct 796 ms 39256 KB Output is correct
35 Correct 506 ms 31276 KB Output is correct
36 Correct 421 ms 48780 KB Output is correct
37 Correct 403 ms 48900 KB Output is correct
38 Correct 860 ms 38304 KB Output is correct
39 Correct 767 ms 37988 KB Output is correct
40 Correct 784 ms 39384 KB Output is correct
41 Correct 414 ms 32296 KB Output is correct
42 Correct 443 ms 32240 KB Output is correct
43 Correct 417 ms 32368 KB Output is correct
44 Correct 445 ms 32236 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8832 KB Output is correct
2 Correct 7 ms 8832 KB Output is correct
3 Correct 8 ms 8960 KB Output is correct
4 Correct 6 ms 8832 KB Output is correct
5 Correct 6 ms 8832 KB Output is correct
6 Correct 6 ms 8832 KB Output is correct
7 Correct 7 ms 8832 KB Output is correct
8 Correct 6 ms 8832 KB Output is correct
9 Correct 8 ms 9088 KB Output is correct
10 Correct 8 ms 9088 KB Output is correct
11 Correct 7 ms 9088 KB Output is correct
12 Correct 8 ms 9088 KB Output is correct
13 Correct 8 ms 9088 KB Output is correct
14 Correct 7 ms 9088 KB Output is correct
15 Correct 8 ms 9088 KB Output is correct
16 Correct 8 ms 9088 KB Output is correct
17 Correct 711 ms 35148 KB Output is correct
18 Correct 772 ms 35484 KB Output is correct
19 Correct 780 ms 35000 KB Output is correct
20 Correct 798 ms 34936 KB Output is correct
21 Correct 692 ms 35036 KB Output is correct
22 Correct 770 ms 35576 KB Output is correct
23 Correct 765 ms 35576 KB Output is correct
24 Correct 770 ms 35580 KB Output is correct
25 Correct 832 ms 35624 KB Output is correct
26 Correct 752 ms 35192 KB Output is correct
27 Correct 746 ms 35192 KB Output is correct
28 Correct 763 ms 35812 KB Output is correct
29 Correct 716 ms 35304 KB Output is correct
30 Correct 761 ms 35192 KB Output is correct
31 Correct 699 ms 35192 KB Output is correct
32 Correct 817 ms 35480 KB Output is correct
33 Correct 741 ms 38368 KB Output is correct
34 Correct 359 ms 31624 KB Output is correct
35 Correct 542 ms 29092 KB Output is correct
36 Correct 517 ms 29048 KB Output is correct
37 Correct 497 ms 28920 KB Output is correct
38 Correct 462 ms 29048 KB Output is correct
39 Correct 486 ms 29048 KB Output is correct
40 Correct 468 ms 29048 KB Output is correct
41 Correct 466 ms 29048 KB Output is correct
42 Correct 473 ms 29176 KB Output is correct
43 Correct 476 ms 29176 KB Output is correct
44 Correct 843 ms 38624 KB Output is correct
45 Correct 468 ms 29176 KB Output is correct
46 Correct 261 ms 36588 KB Output is correct
47 Correct 248 ms 37164 KB Output is correct
48 Correct 720 ms 39512 KB Output is correct
49 Correct 754 ms 37896 KB Output is correct
50 Correct 726 ms 39264 KB Output is correct
51 Correct 337 ms 31480 KB Output is correct
52 Correct 353 ms 31608 KB Output is correct
53 Correct 363 ms 31500 KB Output is correct
54 Correct 342 ms 31480 KB Output is correct
55 Correct 794 ms 39484 KB Output is correct
56 Correct 421 ms 32492 KB Output is correct
57 Correct 458 ms 29000 KB Output is correct
58 Correct 530 ms 31156 KB Output is correct
59 Correct 489 ms 31068 KB Output is correct
60 Correct 465 ms 29492 KB Output is correct
61 Correct 498 ms 33188 KB Output is correct
62 Correct 478 ms 31052 KB Output is correct
63 Correct 486 ms 31396 KB Output is correct
64 Correct 529 ms 31216 KB Output is correct
65 Correct 514 ms 30256 KB Output is correct
66 Correct 796 ms 39256 KB Output is correct
67 Correct 506 ms 31276 KB Output is correct
68 Correct 421 ms 48780 KB Output is correct
69 Correct 403 ms 48900 KB Output is correct
70 Correct 860 ms 38304 KB Output is correct
71 Correct 767 ms 37988 KB Output is correct
72 Correct 784 ms 39384 KB Output is correct
73 Correct 414 ms 32296 KB Output is correct
74 Correct 443 ms 32240 KB Output is correct
75 Correct 417 ms 32368 KB Output is correct
76 Correct 445 ms 32236 KB Output is correct
77 Correct 866 ms 38904 KB Output is correct
78 Correct 412 ms 32368 KB Output is correct
79 Correct 572 ms 31276 KB Output is correct
80 Correct 507 ms 31188 KB Output is correct
81 Correct 481 ms 31152 KB Output is correct
82 Correct 527 ms 33068 KB Output is correct
83 Correct 553 ms 33320 KB Output is correct
84 Correct 521 ms 31280 KB Output is correct
85 Correct 509 ms 31196 KB Output is correct
86 Correct 512 ms 31148 KB Output is correct
87 Correct 508 ms 31436 KB Output is correct
88 Correct 881 ms 38752 KB Output is correct
89 Correct 490 ms 31276 KB Output is correct
90 Correct 413 ms 48784 KB Output is correct
91 Correct 390 ms 45340 KB Output is correct
92 Correct 905 ms 39512 KB Output is correct
93 Correct 787 ms 38420 KB Output is correct
94 Correct 841 ms 38872 KB Output is correct
95 Correct 410 ms 32332 KB Output is correct
96 Correct 413 ms 32240 KB Output is correct
97 Correct 406 ms 32248 KB Output is correct
98 Correct 396 ms 32240 KB Output is correct