Submission #834438

#	Time	Username	Problem	Language	Result	Execution time	Memory
834438		_martynas	Aesthetic (NOI20_aesthetic)	C++11	38 / 100	751 ms	77508 KiB

Aesthetic

    #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 (stderr)

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

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 7 / 7
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16
• Subtask 6: 0 / 22
• Subtask 7: 0 / 27