Submission #833802

#	Time	Username	Problem	Language	Result	Execution time	Memory
833802		_martynas	Aesthetic (NOI20_aesthetic)	C++11	13 / 100	2043 ms	26168 KiB

Aesthetic

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int mxn = 3e5+5;
const ll inf = 1e16;

struct Edge {
    int to, id;
};

int n, m;
vector<Edge> adj[mxn];
ll W[mxn];

ll get_min_dist() {
    vector<long long> dist(n+1, inf);
    priority_queue<pair<ll, int>> pq;
    dist[1] = 0;
    pq.push({-dist[1], 1});;
    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[n];
}

int main(int argc, char const *argv[]) {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b >> W[i];
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    ll mxw = W[m], ans = 0;
    for(int i = m-1; i >= 1; i--) {
        W[i] += mxw;
        ans = max(ans, get_min_dist());
        W[i] -= mxw;
        mxw = max(mxw, W[i]);
    }
    cout << ans << "\n";
    return 0;
}

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