oj.uz

Submission #834158

# Submission time Handle Problem Language Result Execution time Memory
834158 2023-08-22T11:21:39 Z _martynas Aesthetic (NOI20_aesthetic) C++11
13 / 100
 269 ms 536 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#warning change mxn
const int mxn = 3e3+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<ll> get_min_dist(int start, int forb) {
    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] && e.id != forb) {
            dist[e.to] = d+W[e.id];
            pq.push({-dist[e.to], e.to});
        }
    }
    return dist;
}

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});
    }
    vector<ll> from1, fromn;
    from1 = get_min_dist(1, -1);
    fromn = get_min_dist(n, -1);
    ll mxw = W[m];
    vector<ll> ans(m);
    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]);
    }
    for(int i = m-1; i >= 1; i--) {
        ans[i] = min(ans[i], get_min_dist(1, i)[n]);
    }
    ll answer = 0;
    for(int i = 1; i < m; i++) {
        answer = max(answer, ans[i]);
    }
    cout << answer << "\n";
    return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 261 ms 536 KB Output is correct
10 Correct 269 ms 528 KB Output is correct
11 Correct 197 ms 500 KB Output is correct
12 Correct 201 ms 504 KB Output is correct
13 Correct 95 ms 504 KB Output is correct
14 Correct 99 ms 488 KB Output is correct
15 Correct 105 ms 488 KB Output is correct
16 Correct 99 ms 484 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 261 ms 536 KB Output is correct
10 Correct 269 ms 528 KB Output is correct
11 Correct 197 ms 500 KB Output is correct
12 Correct 201 ms 504 KB Output is correct
13 Correct 95 ms 504 KB Output is correct
14 Correct 99 ms 488 KB Output is correct
15 Correct 105 ms 488 KB Output is correct
16 Correct 99 ms 484 KB Output is correct
17 Runtime error 1 ms 468 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -