oj.uz

Submission #892700

# Submission time Handle Problem Language Result Execution time Memory
892700 2023-12-25T17:16:21 Z vjudge1 Aesthetic (NOI20_aesthetic) C++17
100 / 100
 1731 ms 65108 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 3e5 + 5;
const int mxM = 3e5 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;

int n, m;
bool vis[mxN];
vector<pair<int, int>> G[mxN], Gn[mxN];
int w[mxM], max_w[mxM];
i64 dis1[mxN], disn[mxN];
pair<int, int> edges[mxM];

i64 dijkstra() {
    fill(dis1 + 1, dis1 + n + 1, oo);
    priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;

    dis1[1] = 0; pq.emplace(0, 1);
    while (not pq.empty()) {
        i64 cdis = pq.top().ff;
        int v = pq.top().ss;
        pq.pop();
        if (cdis != dis1[v]) continue;
        for (auto [u, ei] : G[v]) {
            if (dis1[v] + w[ei] < dis1[u]) {
                dis1[u] = dis1[v] + w[ei];
                pq.emplace(dis1[u], u);
            }
        }
    }

    fill(disn + 1, disn + n + 1, oo);
    disn[n] = 0; pq.emplace(0, n);
    while (not pq.empty()) {
        i64 cdis = pq.top().ff;
        int v = pq.top().ss;
        pq.pop();
        if (cdis != disn[v]) continue;
        for (auto [u, ei] : G[v]) {
            if (disn[v] + w[ei] < disn[u]) {
                disn[u] = disn[v] + w[ei];
                pq.emplace(disn[u], u);
            }
        }
    }

    return dis1[n];
}

i64 res_check;
bool vis_n[mxN];
int low[mxN], tin[mxN], tdfs;

void reset_check() {
    res_check = -1, tdfs = 0;
    for (int i = 1; i <= n; ++i) {
        G[i].clear();
        vis[i] = vis_n[i] = false;
    }
}

void dfs(int v, int p) {
    vis[v] = true, vis_n[v] = (v == n);
    tin[v] = low[v] = ++tdfs;
    for (auto [u, ei] : G[v]) {
        if (u == p) continue;
        if (vis[u]) {
            low[v] = min(low[v], tin[u]);
        }
        else {
            dfs(u, v);
            low[v] = min(low[v], low[u]);
            if (low[u] > tin[v] && vis_n[u]) {
                res_check = max(res_check, min(dis1[u] + disn[v], dis1[v] + disn[u]) + w[ei] + max_w[ei]);
            }
            vis_n[v] |= vis_n[u];
        }
    }
}

bool check(i64 val) {
    reset_check();
    for (int i = 1; i <= m; ++i) {
        int u = edges[i].ff, v = edges[i].ss;
        if (min(dis1[u] + disn[v], dis1[v] + disn[u]) + w[i] <= val) {
            // cout << u << " " << v << endl;
            G[u].emplace_back(v, i);
            G[v].emplace_back(u, i);
        }
    }
    dfs(1, 0);
    // cout << res_check << endl << endl;
    return !(res_check > val);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, cw;
        cin >> u >> v >> cw;
        G[u].emplace_back(v, i);
        G[v].emplace_back(u, i);
        edges[i] = {u, v};
        w[i] = max_w[i - 1] = cw;
    }
    for (int i = m - 1; i >= 1; --i)
        max_w[i] = max(max_w[i], max_w[i + 1]);

    i64 miin = dijkstra();
    i64 l = miin, r = miin + 1e9;
    while (l < r) {
        i64 mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 50392 KB Output is correct
2 Correct 380 ms 50064 KB Output is correct
3 Correct 378 ms 50000 KB Output is correct
4 Correct 384 ms 50052 KB Output is correct
5 Correct 409 ms 50180 KB Output is correct
6 Correct 382 ms 50260 KB Output is correct
7 Correct 379 ms 50256 KB Output is correct
8 Correct 413 ms 50440 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 50552 KB Output is correct
2 Correct 430 ms 50512 KB Output is correct
3 Correct 349 ms 50064 KB Output is correct
4 Correct 370 ms 50444 KB Output is correct
5 Correct 404 ms 50156 KB Output is correct
6 Correct 384 ms 50180 KB Output is correct
7 Correct 357 ms 50172 KB Output is correct
8 Correct 410 ms 50284 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1731 ms 58296 KB Output is correct
2 Correct 636 ms 47960 KB Output is correct
3 Correct 983 ms 55600 KB Output is correct
4 Correct 922 ms 55636 KB Output is correct
5 Correct 912 ms 55576 KB Output is correct
6 Correct 971 ms 55548 KB Output is correct
7 Correct 959 ms 55892 KB Output is correct
8 Correct 1018 ms 55788 KB Output is correct
9 Correct 935 ms 55836 KB Output is correct
10 Correct 1028 ms 56148 KB Output is correct
11 Correct 924 ms 55764 KB Output is correct
12 Correct 1692 ms 58888 KB Output is correct
13 Correct 950 ms 55728 KB Output is correct
14 Correct 368 ms 64876 KB Output is correct
15 Correct 341 ms 65108 KB Output is correct
16 Correct 1710 ms 58940 KB Output is correct
17 Correct 1613 ms 58428 KB Output is correct
18 Correct 1643 ms 58816 KB Output is correct
19 Correct 658 ms 47944 KB Output is correct
20 Correct 631 ms 47984 KB Output is correct
21 Correct 668 ms 47964 KB Output is correct
22 Correct 636 ms 47952 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1731 ms 58296 KB Output is correct
2 Correct 636 ms 47960 KB Output is correct
3 Correct 983 ms 55600 KB Output is correct
4 Correct 922 ms 55636 KB Output is correct
5 Correct 912 ms 55576 KB Output is correct
6 Correct 971 ms 55548 KB Output is correct
7 Correct 959 ms 55892 KB Output is correct
8 Correct 1018 ms 55788 KB Output is correct
9 Correct 935 ms 55836 KB Output is correct
10 Correct 1028 ms 56148 KB Output is correct
11 Correct 924 ms 55764 KB Output is correct
12 Correct 1692 ms 58888 KB Output is correct
13 Correct 950 ms 55728 KB Output is correct
14 Correct 368 ms 64876 KB Output is correct
15 Correct 341 ms 65108 KB Output is correct
16 Correct 1710 ms 58940 KB Output is correct
17 Correct 1613 ms 58428 KB Output is correct
18 Correct 1643 ms 58816 KB Output is correct
19 Correct 658 ms 47944 KB Output is correct
20 Correct 631 ms 47984 KB Output is correct
21 Correct 668 ms 47964 KB Output is correct
22 Correct 636 ms 47952 KB Output is correct
23 Correct 1621 ms 58864 KB Output is correct
24 Correct 673 ms 48008 KB Output is correct
25 Correct 843 ms 55496 KB Output is correct
26 Correct 885 ms 55532 KB Output is correct
27 Correct 836 ms 55552 KB Output is correct
28 Correct 817 ms 55888 KB Output is correct
29 Correct 880 ms 55692 KB Output is correct
30 Correct 851 ms 55908 KB Output is correct
31 Correct 870 ms 55864 KB Output is correct
32 Correct 884 ms 55512 KB Output is correct
33 Correct 893 ms 55640 KB Output is correct
34 Correct 1546 ms 58720 KB Output is correct
35 Correct 898 ms 55832 KB Output is correct
36 Correct 329 ms 59532 KB Output is correct
37 Correct 335 ms 59992 KB Output is correct
38 Correct 1529 ms 58316 KB Output is correct
39 Correct 1588 ms 58364 KB Output is correct
40 Correct 1523 ms 58860 KB Output is correct
41 Correct 673 ms 47952 KB Output is correct
42 Correct 645 ms 48012 KB Output is correct
43 Correct 670 ms 47988 KB Output is correct
44 Correct 651 ms 48004 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27228 KB Output is correct
2 Correct 5 ms 27228 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 5 ms 27228 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 6 ms 27224 KB Output is correct
10 Correct 6 ms 27228 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 6 ms 27224 KB Output is correct
13 Correct 6 ms 27228 KB Output is correct
14 Correct 6 ms 27228 KB Output is correct
15 Correct 6 ms 27228 KB Output is correct
16 Correct 6 ms 27284 KB Output is correct
17 Correct 388 ms 50392 KB Output is correct
18 Correct 380 ms 50064 KB Output is correct
19 Correct 378 ms 50000 KB Output is correct
20 Correct 384 ms 50052 KB Output is correct
21 Correct 409 ms 50180 KB Output is correct
22 Correct 382 ms 50260 KB Output is correct
23 Correct 379 ms 50256 KB Output is correct
24 Correct 413 ms 50440 KB Output is correct
25 Correct 401 ms 50552 KB Output is correct
26 Correct 430 ms 50512 KB Output is correct
27 Correct 349 ms 50064 KB Output is correct
28 Correct 370 ms 50444 KB Output is correct
29 Correct 404 ms 50156 KB Output is correct
30 Correct 384 ms 50180 KB Output is correct
31 Correct 357 ms 50172 KB Output is correct
32 Correct 410 ms 50284 KB Output is correct
33 Correct 1731 ms 58296 KB Output is correct
34 Correct 636 ms 47960 KB Output is correct
35 Correct 983 ms 55600 KB Output is correct
36 Correct 922 ms 55636 KB Output is correct
37 Correct 912 ms 55576 KB Output is correct
38 Correct 971 ms 55548 KB Output is correct
39 Correct 959 ms 55892 KB Output is correct
40 Correct 1018 ms 55788 KB Output is correct
41 Correct 935 ms 55836 KB Output is correct
42 Correct 1028 ms 56148 KB Output is correct
43 Correct 924 ms 55764 KB Output is correct
44 Correct 1692 ms 58888 KB Output is correct
45 Correct 950 ms 55728 KB Output is correct
46 Correct 368 ms 64876 KB Output is correct
47 Correct 341 ms 65108 KB Output is correct
48 Correct 1710 ms 58940 KB Output is correct
49 Correct 1613 ms 58428 KB Output is correct
50 Correct 1643 ms 58816 KB Output is correct
51 Correct 658 ms 47944 KB Output is correct
52 Correct 631 ms 47984 KB Output is correct
53 Correct 668 ms 47964 KB Output is correct
54 Correct 636 ms 47952 KB Output is correct
55 Correct 1621 ms 58864 KB Output is correct
56 Correct 673 ms 48008 KB Output is correct
57 Correct 843 ms 55496 KB Output is correct
58 Correct 885 ms 55532 KB Output is correct
59 Correct 836 ms 55552 KB Output is correct
60 Correct 817 ms 55888 KB Output is correct
61 Correct 880 ms 55692 KB Output is correct
62 Correct 851 ms 55908 KB Output is correct
63 Correct 870 ms 55864 KB Output is correct
64 Correct 884 ms 55512 KB Output is correct
65 Correct 893 ms 55640 KB Output is correct
66 Correct 1546 ms 58720 KB Output is correct
67 Correct 898 ms 55832 KB Output is correct
68 Correct 329 ms 59532 KB Output is correct
69 Correct 335 ms 59992 KB Output is correct
70 Correct 1529 ms 58316 KB Output is correct
71 Correct 1588 ms 58364 KB Output is correct
72 Correct 1523 ms 58860 KB Output is correct
73 Correct 673 ms 47952 KB Output is correct
74 Correct 645 ms 48012 KB Output is correct
75 Correct 670 ms 47988 KB Output is correct
76 Correct 651 ms 48004 KB Output is correct
77 Correct 333 ms 50236 KB Output is correct
78 Correct 389 ms 47952 KB Output is correct
79 Correct 258 ms 55672 KB Output is correct
80 Correct 305 ms 55428 KB Output is correct
81 Correct 266 ms 55376 KB Output is correct
82 Correct 256 ms 55508 KB Output is correct
83 Correct 258 ms 55808 KB Output is correct
84 Correct 299 ms 55888 KB Output is correct
85 Correct 290 ms 55584 KB Output is correct
86 Correct 284 ms 55600 KB Output is correct
87 Correct 267 ms 55632 KB Output is correct
88 Correct 309 ms 49896 KB Output is correct
89 Correct 284 ms 55768 KB Output is correct
90 Correct 331 ms 60836 KB Output is correct
91 Correct 338 ms 60300 KB Output is correct
92 Correct 342 ms 50108 KB Output is correct
93 Correct 319 ms 49844 KB Output is correct
94 Correct 342 ms 49608 KB Output is correct
95 Correct 359 ms 47852 KB Output is correct
96 Correct 376 ms 47856 KB Output is correct
97 Correct 386 ms 47856 KB Output is correct
98 Correct 370 ms 47700 KB Output is correct