oj.uz

Submission #892697

# Submission time Handle Problem Language Result Execution time Memory
892697 2023-12-25T17:08:23 Z CDuong Aesthetic (NOI20_aesthetic) C++17
16 / 100
 1903 ms 69460 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]) {
                // cout << u << " " << v << " " << ei << " " << w[ei] << " " << max_w[ei] << endl;
                res_check = max(res_check, min(dis1[u] + disn[v], dis1[v] + disn[u]) + w[ei] + max_w[ei]);
            }
            vis_n[v] |= vis[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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Incorrect 5 ms 27228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Incorrect 5 ms 27228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 389 ms 50004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 411 ms 50420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1695 ms 58316 KB Output is correct
2 Correct 628 ms 52400 KB Output is correct
3 Correct 1006 ms 59588 KB Output is correct
4 Correct 978 ms 59728 KB Output is correct
5 Correct 960 ms 59432 KB Output is correct
6 Correct 981 ms 59672 KB Output is correct
7 Correct 1025 ms 59720 KB Output is correct
8 Correct 981 ms 59804 KB Output is correct
9 Correct 938 ms 59644 KB Output is correct
10 Correct 981 ms 59968 KB Output is correct
11 Correct 929 ms 59780 KB Output is correct
12 Correct 1661 ms 63056 KB Output is correct
13 Correct 990 ms 59752 KB Output is correct
14 Correct 354 ms 69460 KB Output is correct
15 Correct 351 ms 69440 KB Output is correct
16 Correct 1645 ms 63544 KB Output is correct
17 Correct 1593 ms 62540 KB Output is correct
18 Correct 1629 ms 62912 KB Output is correct
19 Correct 629 ms 52308 KB Output is correct
20 Correct 638 ms 52428 KB Output is correct
21 Correct 640 ms 52484 KB Output is correct
22 Correct 640 ms 52284 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1695 ms 58316 KB Output is correct
2 Correct 628 ms 52400 KB Output is correct
3 Correct 1006 ms 59588 KB Output is correct
4 Correct 978 ms 59728 KB Output is correct
5 Correct 960 ms 59432 KB Output is correct
6 Correct 981 ms 59672 KB Output is correct
7 Correct 1025 ms 59720 KB Output is correct
8 Correct 981 ms 59804 KB Output is correct
9 Correct 938 ms 59644 KB Output is correct
10 Correct 981 ms 59968 KB Output is correct
11 Correct 929 ms 59780 KB Output is correct
12 Correct 1661 ms 63056 KB Output is correct
13 Correct 990 ms 59752 KB Output is correct
14 Correct 354 ms 69460 KB Output is correct
15 Correct 351 ms 69440 KB Output is correct
16 Correct 1645 ms 63544 KB Output is correct
17 Correct 1593 ms 62540 KB Output is correct
18 Correct 1629 ms 62912 KB Output is correct
19 Correct 629 ms 52308 KB Output is correct
20 Correct 638 ms 52428 KB Output is correct
21 Correct 640 ms 52484 KB Output is correct
22 Correct 640 ms 52284 KB Output is correct
23 Incorrect 1903 ms 63388 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Incorrect 5 ms 27228 KB Output isn't correct
3 Halted 0 ms 0 KB -