oj.uz

Submission #602394

# Submission time Handle Problem Language Result Execution time Memory
602394 2022-07-23T03:29:51 Z verngutz Aesthetic (NOI20_aesthetic) C++17
5 / 100
 2000 ms 34544 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});
    }
    auto [d, p] = sssp(g, {1});
    ll ans = d[n];
    for(int i = 0; i < m; i++) {
        for(int j = i + 1; j < m; j++) {
            g.edges[i << 1].w += g.edges[j << 1].w;
            g.edges[(i << 1) | 1].w += g.edges[j << 1].w;
            auto [d2, p2] = sssp(g, {1});
            ans = max(ans, d2[n]);
            g.edges[i << 1].w -= g.edges[j << 1].w;
            g.edges[(i << 1) | 1].w -= g.edges[j << 1].w;
        }
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 328 KB Output is correct
2 Correct 15 ms 444 KB Output is correct
3 Correct 11 ms 328 KB Output is correct
4 Correct 10 ms 332 KB Output is correct
5 Correct 7 ms 212 KB Output is correct
6 Correct 8 ms 336 KB Output is correct
7 Correct 7 ms 212 KB Output is correct
8 Correct 9 ms 212 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 328 KB Output is correct
2 Correct 15 ms 444 KB Output is correct
3 Correct 11 ms 328 KB Output is correct
4 Correct 10 ms 332 KB Output is correct
5 Correct 7 ms 212 KB Output is correct
6 Correct 8 ms 336 KB Output is correct
7 Correct 7 ms 212 KB Output is correct
8 Correct 9 ms 212 KB Output is correct
9 Execution timed out 2063 ms 468 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 33856 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 2083 ms 34544 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 2041 ms 29404 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 2041 ms 29404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 328 KB Output is correct
2 Correct 15 ms 444 KB Output is correct
3 Correct 11 ms 328 KB Output is correct
4 Correct 10 ms 332 KB Output is correct
5 Correct 7 ms 212 KB Output is correct
6 Correct 8 ms 336 KB Output is correct
7 Correct 7 ms 212 KB Output is correct
8 Correct 9 ms 212 KB Output is correct
9 Execution timed out 2063 ms 468 KB Time limit exceeded
10 Halted 0 ms 0 KB -