oj.uz

Submission #833802

# Submission time Handle Problem Language Result Execution time Memory
833802 2023-08-22T08:43:38 Z _martynas Aesthetic (NOI20_aesthetic) C++11
13 / 100
 2000 ms 26168 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 3 ms 7352 KB Output is correct
4 Correct 3 ms 7252 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7348 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 3 ms 7352 KB Output is correct
4 Correct 3 ms 7252 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7348 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 267 ms 7484 KB Output is correct
10 Correct 272 ms 7380 KB Output is correct
11 Correct 205 ms 7380 KB Output is correct
12 Correct 213 ms 7456 KB Output is correct
13 Correct 95 ms 7444 KB Output is correct
14 Correct 99 ms 7380 KB Output is correct
15 Correct 106 ms 7448 KB Output is correct
16 Correct 99 ms 7380 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2024 ms 25820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2011 ms 26168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2043 ms 25420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2043 ms 25420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7252 KB Output is correct
2 Correct 4 ms 7252 KB Output is correct
3 Correct 3 ms 7352 KB Output is correct
4 Correct 3 ms 7252 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 3 ms 7348 KB Output is correct
7 Correct 4 ms 7252 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 267 ms 7484 KB Output is correct
10 Correct 272 ms 7380 KB Output is correct
11 Correct 205 ms 7380 KB Output is correct
12 Correct 213 ms 7456 KB Output is correct
13 Correct 95 ms 7444 KB Output is correct
14 Correct 99 ms 7380 KB Output is correct
15 Correct 106 ms 7448 KB Output is correct
16 Correct 99 ms 7380 KB Output is correct
17 Execution timed out 2024 ms 25820 KB Time limit exceeded
18 Halted 0 ms 0 KB -