oj.uz

Submission #602818

# Submission time Handle Problem Language Result Execution time Memory
602818 2022-07-23T11:35:14 Z verngutz Aesthetic (NOI20_aesthetic) C++17
13 / 100
 2000 ms 37792 KB 
#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
template <typename T> struct wedge {
    int u, v; T w;
    wedge reverse() const { return {v, u, w}; }
    friend ostream& operator<<(ostream& os, const wedge& e) {
        return os << "{u: " << e.u << ", v: " << e.v << ", w: " << e.w << "}";
    }
};
template <bool Directed, typename TEdge, bool Index> struct graph {
    using EType = TEdge;
    vector<TEdge> edges;
    vector<vector<int>> adj;
    graph(int n) : adj(n + Index) {}
    graph(int n, int m) : graph(n) { edges.reserve(m << not Directed); }
    TEdge& operator()(int e) { return edges[e]; }
    vector<int>& operator[](int u) { return adj[u]; }
    int size() { return adj.size() - Index; }
    void append(int u, const TEdge& e) {
        adj[u].push_back(edges.size());
        edges.push_back(e);
    }
    void add_edge(const TEdge& e) {
        append(e.u, e);
        if(not Directed) append(e.v, e.reverse());
    }
};
template <bool Directed, typename T, bool Index>
pair<vector<T>, vector<int>> sssp(graph<Directed, wedge<T>, Index>& g, const vector<int>& s) {
    vector<int> vis(g.adj.size()), p(g.adj.size(), -1);
    vector<T> d(g.adj.size(), lim<T>::max());
    priority_queue<pair<T, int>> pq;
    for(int u : s) {
        pq.push({d[u] = 0, u});
    }
    while(not pq.empty()) {
        int u = pq.top().second; pq.pop();
        if(not vis[u]) {
            vis[u] = true;
            for(int e : g[u]) {
                if(not vis[g(e).v] and d[g(e).v] > d[u] + g(e).w) {
                    pq.push({-(d[g(e).v] = d[u] + g(e).w), g(p[g(e).v] = e).v});
                }
            }
        }
    }
    return {move(d), move(p)};
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    graph<0, wedge<ll>, 1> g(n, m);
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.add_edge({u, v, w});
    }
    ll max_replace = 0;
    ll ans = sssp(g, {1}).first[n];
    for(int i = m - 1; i >= 0; i--) {
        g.edges[2 * i].w += max_replace;
        g.edges[2 * i + 1].w += max_replace;
        ans = max(ans, sssp(g, {1}).first[n]);
        g.edges[2 * i].w -= max_replace;
        g.edges[2 * i + 1].w -= max_replace;
        max_replace = max(max_replace, g.edges[2 * i].w);
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 272 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 329 ms 516 KB Output is correct
10 Correct 327 ms 468 KB Output is correct
11 Correct 236 ms 508 KB Output is correct
12 Correct 248 ms 512 KB Output is correct
13 Correct 141 ms 472 KB Output is correct
14 Correct 150 ms 476 KB Output is correct
15 Correct 170 ms 492 KB Output is correct
16 Correct 146 ms 472 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 36936 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 2072 ms 37792 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 2048 ms 31164 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 2048 ms 31164 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 272 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 329 ms 516 KB Output is correct
10 Correct 327 ms 468 KB Output is correct
11 Correct 236 ms 508 KB Output is correct
12 Correct 248 ms 512 KB Output is correct
13 Correct 141 ms 472 KB Output is correct
14 Correct 150 ms 476 KB Output is correct
15 Correct 170 ms 492 KB Output is correct
16 Correct 146 ms 472 KB Output is correct
17 Execution timed out 2076 ms 36936 KB Time limit exceeded
18 Halted 0 ms 0 KB -