Submission #834458

#	Time	Username	Problem	Language	Result	Execution time	Memory
834458		_martynas	Aesthetic (NOI20_aesthetic)	C++11	38 / 100	742 ms	77244 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];
bool onpathton[mxn];
void bridge_det(int u, int par) {
    visited[u] = true;
    if(u == n) onpathton[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] && onpathton[e.to]) {
                isbridge[e.id] = true;
            }
        }
        onpathton[u] = onpathton[u] || onpathton[e.to];
        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()) {
            // cerr << cnt_to_id[i] << " <- " << (*available.begin()) << "\n";
            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:2: 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