oj.uz

Submission #834438

# Submission time Handle Problem Language Result Execution time Memory
834438 2023-08-22T14:17:51 Z _martynas Aesthetic (NOI20_aesthetic) C++11
38 / 100
 751 ms 77508 KB 
    #include <bits/stdc++.h>
     
    using namespace std;
     
    using ll = long long;
     
    #warning change mxn
    const int mxn = 3e5+5;
    const ll inf = 1e16;
     
    struct Edge {
        int to, id;
    };
     
    int n, m;
    int A[mxn], B[mxn];
    vector<Edge> adj[mxn];
    ll W[mxn];
    vector<Edge> adj2[mxn];
    bool isbridge[mxn], visited[mxn];
    vector<ll> from1, fromn;
     
    vector<ll> get_min_dist(int start) {
        vector<long long> dist(n+1, inf);
        priority_queue<pair<ll, int>> pq;
        dist[start] = 0;
        pq.push({-dist[start], start});;
        while(!pq.empty()) {
            ll d = -pq.top().first;
            int a = pq.top().second;
            pq.pop();
            if(dist[a] != d) continue;
            for(auto e : adj[a]) if(dist[e.to] > d+W[e.id]) {
                dist[e.to] = d+W[e.id];
                pq.push({-dist[e.to], e.to});
            }
        }
        return dist;
    }
     
     
    int tim = 0;
    int disc[mxn], low[mxn];
    void bridge_det(int u, int par) {
        visited[u] = true;
        low[u] = disc[u] = tim++;
        for(auto e : adj2[u]) if(e.to != par) {
            if(!visited[e.to]) {
                bridge_det(e.to, u);
                if(low[e.to] > disc[u]) {
                    isbridge[e.id] = true;
                }
            }
            low[u] = min(low[u], low[e.to]);
        }
    }
     
    int main(int argc, char const *argv[]) {
        cin >> n >> m;
        for(int i = 1; i <= m; i++) {
            cin >> A[i] >> B[i] >> W[i];
            adj[A[i]].push_back({B[i], i});
            adj[B[i]].push_back({A[i], i});
        }
        from1 = get_min_dist(1);
        fromn = get_min_dist(n);
        ll mxw = W[m];
        vector<ll> ans(m+1);
        for(int i = m-1; i >= 1; i--) {
            ll nw = W[i]+mxw;
            ll mndist = inf;
            mndist = min(mndist, from1[A[i]]+fromn[B[i]]+nw);
            mndist = min(mndist, from1[B[i]]+fromn[A[i]]+nw);
            ans[i] = mndist;
            mxw = max(mxw, W[i]);
        }
        // build new graph where every path is min
        for(int i = 1; i <= m; i++) {
            if(from1[A[i]]+fromn[B[i]]+W[i] == from1[n] || from1[B[i]]+fromn[A[i]]+W[i] == from1[n]) {
                adj2[A[i]].push_back({B[i], i});
                adj2[B[i]].push_back({A[i], i});
            }
        }
        // printf("new graph\n");
        // for(int i = 1; i <= n; i++) {
        //     printf("%d: ", i);
        //     for(auto e : adj2[i]) {
        //         printf("%d (%d), ", e.to, e.id);
        //     }
        //     printf("\n");
        // }
        fill(low, low+n+1, mxn);
        bridge_det(1, -1);
        // printf("bridge: ");
        // for(int i = m; i >= 1; i--) if(isbridge[i]) printf("%d ", i);
        // printf("\n");
        vector<int> cnt_to_id(m+1);
        fill(visited, visited+n+1, false);
        queue<int> q;
        visited[1] = true; q.push(1);
        int c = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            for(auto e : adj2[u]) if(!visited[e.to]) {
                visited[e.to] = true;
                c += isbridge[e.id];
                cnt_to_id[c] = e.id;
            }
        }
        vector<long long> dist(n+1, inf);
        vector<int> cnt(n+1);
        priority_queue<pair<pair<ll, int>, int>> pq;
        vector<Edge> used_edge; vector<int> from;
        dist[1] = 0, cnt[1] = 0;
        pq.push({{-dist[1], 1}, -1});
        vector<vector<ll>> ins(m+1), del(m+1);
        while(!pq.empty()) {
            ll d = -pq.top().first.first;
            int a = pq.top().first.second;
            int edgeidx = pq.top().second;
            pq.pop();
            if(edgeidx != -1) {
                // cerr << from[edgeidx] << " -> " << a << "\n";
                // cerr << cnt[from[edgeidx]]+isbridge[used_edge[edgeidx].id] << "; " << cnt[a] << "\n";
                if(cnt[used_edge[edgeidx].to] > cnt[from[edgeidx]]+isbridge[used_edge[edgeidx].id]) {
                    int l = cnt[from[edgeidx]]+isbridge[used_edge[edgeidx].id]+1, r = cnt[a];
                    ll val = from1[from[edgeidx]]+W[used_edge[edgeidx].id]+fromn[a];
                    // for(int i = l; i <= r; i++) {
                    //     // cerr << "modify " << cnt_to_id[i] << "\n";
                    //     ans[cnt_to_id[i]] = min(ans[cnt_to_id[i]], val);
                    // }
                    ins[l].push_back(val);
                    del[r].push_back(val);
                }
            }
            if(dist[a] != d) continue;
            // cerr << a << " " << d << "\n";
            for(auto e : adj[a]) {
                if(dist[e.to] > d+W[e.id]) {
                    cnt[e.to] = cnt[a]+isbridge[e.id];
                    dist[e.to] = d+W[e.id];
                    pq.push({{-dist[e.to], e.to}, used_edge.size()});
                    used_edge.push_back(e); from.push_back(a);
                    // cerr << "add " << from.back() << " " << used_edge.back().to << "\n";
                }
                else {
                    // cerr << a << " -> " << e.to << "\n";
                    // cerr << cnt[a]+isbridge[e.id] << "; " << cnt[e.to] << "\n";
                    if(cnt[e.to] > cnt[a]+isbridge[e.id]) {
                        int l = cnt[a]+isbridge[e.id]+1, r = cnt[e.to];
                        ll val = from1[a]+W[e.id]+fromn[e.to];
                        // for(int i = l; i <= r; i++)  {
                        //     // cerr << i << ": " << cnt_to_id[i] << "?\n";
                        //     ans[cnt_to_id[i]] = min(ans[cnt_to_id[i]], val);
                        // }
                        ins[l].push_back(val);
                        del[r].push_back(val);
                    }
                }
            }
        }
        multiset<ll> available;
        for(int i = 0; i < m; i++) {
            for(ll x : ins[i]) available.insert(x);
            if(cnt_to_id[i] != 0 && !available.empty()) {
                ans[cnt_to_id[i]] = min(ans[cnt_to_id[i]], *available.begin());
            }
            for(ll x : del[i]) available.erase(available.find(x));
        }
        ll answer = 0;
        for(int i = 1; i < m; i++) {
            // cerr << ans[i] << " ";
            answer = max(answer, isbridge[i] ? ans[i] : from1[n]);
        }
        // cerr << "\n";
        cout << answer << "\n";
        return 0;
    }

Compilation message

Aesthetic.cpp:7:6: warning: #warning change mxn [-Wcpp]
    7 |     #warning change mxn
      |      ^~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 64704 KB Output is correct
2 Correct 604 ms 64776 KB Output is correct
3 Correct 631 ms 64316 KB Output is correct
4 Correct 686 ms 64344 KB Output is correct
5 Correct 658 ms 64592 KB Output is correct
6 Correct 603 ms 65488 KB Output is correct
7 Correct 660 ms 65164 KB Output is correct
8 Correct 618 ms 65660 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 65596 KB Output is correct
2 Correct 751 ms 65336 KB Output is correct
3 Correct 728 ms 64696 KB Output is correct
4 Correct 642 ms 65000 KB Output is correct
5 Correct 713 ms 65084 KB Output is correct
6 Correct 703 ms 65156 KB Output is correct
7 Correct 736 ms 65144 KB Output is correct
8 Correct 717 ms 65548 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 58596 KB Output is correct
2 Correct 327 ms 60092 KB Output is correct
3 Correct 416 ms 65608 KB Output is correct
4 Correct 384 ms 65700 KB Output is correct
5 Correct 417 ms 65644 KB Output is correct
6 Correct 411 ms 65732 KB Output is correct
7 Correct 366 ms 65736 KB Output is correct
8 Correct 387 ms 65860 KB Output is correct
9 Correct 420 ms 65740 KB Output is correct
10 Correct 378 ms 66100 KB Output is correct
11 Correct 410 ms 65820 KB Output is correct
12 Correct 492 ms 60976 KB Output is correct
13 Correct 377 ms 65916 KB Output is correct
14 Correct 297 ms 76108 KB Output is correct
15 Correct 267 ms 77508 KB Output is correct
16 Correct 468 ms 62920 KB Output is correct
17 Correct 580 ms 63588 KB Output is correct
18 Correct 513 ms 62472 KB Output is correct
19 Correct 343 ms 63860 KB Output is correct
20 Correct 331 ms 63908 KB Output is correct
21 Correct 322 ms 63880 KB Output is correct
22 Correct 316 ms 63976 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 571 ms 58596 KB Output is correct
2 Correct 327 ms 60092 KB Output is correct
3 Correct 416 ms 65608 KB Output is correct
4 Correct 384 ms 65700 KB Output is correct
5 Correct 417 ms 65644 KB Output is correct
6 Correct 411 ms 65732 KB Output is correct
7 Correct 366 ms 65736 KB Output is correct
8 Correct 387 ms 65860 KB Output is correct
9 Correct 420 ms 65740 KB Output is correct
10 Correct 378 ms 66100 KB Output is correct
11 Correct 410 ms 65820 KB Output is correct
12 Correct 492 ms 60976 KB Output is correct
13 Correct 377 ms 65916 KB Output is correct
14 Correct 297 ms 76108 KB Output is correct
15 Correct 267 ms 77508 KB Output is correct
16 Correct 468 ms 62920 KB Output is correct
17 Correct 580 ms 63588 KB Output is correct
18 Correct 513 ms 62472 KB Output is correct
19 Correct 343 ms 63860 KB Output is correct
20 Correct 331 ms 63908 KB Output is correct
21 Correct 322 ms 63880 KB Output is correct
22 Correct 316 ms 63976 KB Output is correct
23 Correct 611 ms 66352 KB Output is correct
24 Correct 375 ms 66368 KB Output is correct
25 Correct 318 ms 54696 KB Output is correct
26 Incorrect 353 ms 58080 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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