oj.uz

Submission #603454

# Submission time Handle Problem Language Result Execution time Memory
603454 2022-07-24T07:07:20 Z verngutz Aesthetic (NOI20_aesthetic) C++17
16 / 100
 1560 ms 124700 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;
    int i; T dw;
    wedge reverse() const { return {v, u, w, i, dw}; }
    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)};
}
template <bool Directed, typename TEdge, bool Index>
vector<int> construct_path(graph<Directed, TEdge, Index>& g, const vector<int>& parent, int t) {
    vector<int> ans = {t};
    while(parent[ans.back()] != -1) {
        ans.push_back(g(parent[ans.back()]).u);
    }
    reverse(ans.begin(), ans.end());
    return ans;
}
template <typename TEdge, bool Index> pair<vector<int>, vector<vector<int>>> find_2eccs(graph<0, TEdge, Index>& g) {
    vector<int> vis(g.adj.size()), low(g.adj.size()), cut_edge(g.edges.size()), s;
    vector<vector<int>> _2eccs = {};
    int timer = 1;
    function<void(int, int)> dfs = [&](int u, int from) {
        vis[u] = low[u] = timer++;
        s.push_back(u);
        for(int e : g[u]) {
            if(not vis[g(e).v]) {
                dfs(g(e).v, e & ~1);
                if(vis[u] < low[g(e).v]) {
                    cut_edge[e] = cut_edge[e ^ 1] = true;
                    _2eccs.push_back(vector<int>());
                    do {
                        _2eccs.back().push_back(s.back()), s.pop_back();
                    } while(_2eccs.back().back() != g(e).v);
                }
                low[u] = min(low[u], low[g(e).v]);
            } else if((e & ~1) != from and vis[u] > vis[g(e).v]) {
                low[u] = min(low[u], vis[g(e).v]);
            }
        }
    };
    for(int u = Index; u < g.adj.size(); u++) if(not vis[u]) {
        dfs(u, -1);
        _2eccs.push_back(vector<int>());
        while(not s.empty()) {
            _2eccs.back().push_back(s.back()), s.pop_back();
        }
    }
    return {move(cut_edge), move(_2eccs)};
}
template <typename TEdge, bool Index> pair<vector<int>, graph<0, TEdge, Index>> build_bridge_tree(graph<0, TEdge, Index>& g,
const vector<int>& cut_edge, const vector<vector<int>>& _2eccs) {
    vector<int> _2ecc_id(g.adj.size());
    for(int i = 0; i < _2eccs.size(); i++) {
        for(int u : _2eccs[i]) {
            _2ecc_id[u] = i + Index;
        }
    }
    graph<0, TEdge, Index> bridge_tree(_2eccs.size());
    for(int e = 0; e < g.edges.size(); e++) {
        if(cut_edge[e] and g(e).u < g(e).v) {
            bridge_tree.add_edge({_2ecc_id[g(e).u], _2ecc_id[g(e).v]});
        }
    }
    return {move(_2ecc_id), move(bridge_tree)};
}
template <typename TEdge, bool Index> pair<vector<int>, graph<0, TEdge, Index>> build_bridge_tree(graph<0, TEdge, Index>& g) {
    auto [cut_edge, _2eccs] = find_2eccs(g);
    return build_bridge_tree(g, cut_edge, _2eccs);
}
const int MAX_WI = 10;
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, i});
    }
    ll max_dw = 0;
    for(int i = m - 1; i >= 0; i--) {
        g.edges[2 * i].dw = g.edges[2 * i + 1].dw = max_dw;
        max_dw = max(max_dw, g.edges[2 * i].w);
    }
    auto [ds, ps] = sssp(g, {1});
    auto [dt, pt] = sssp(g, {n});
    ll ans = ds[n];
    for(int delta = 1; delta <= MAX_WI; delta++) {
        graph<0, wedge<ll>, 1> sp_dag(n);
        for(int ii = 0; ii < g.edges.size(); ii += 2) {
            auto [u, v, w, i, dw] = g.edges[ii];
            ll uv_path = ds[u] + w + dt[v];
            ll vu_path = ds[v] + w + dt[u];
            if(min(uv_path, vu_path) < ds[n] + delta) {
                if(min(uv_path, vu_path) == uv_path) {
                    sp_dag.add_edge({u, v, w, i, dw});
                } else {
                    sp_dag.add_edge({v, u, w, i, dw});
                }
            }
        }
        auto [cut_edge, _2eccs] = find_2eccs(sp_dag);
        auto [_2ecc_id, bridge_tree] = build_bridge_tree(sp_dag, cut_edge, _2eccs);
        auto [d, p] = sssp(bridge_tree, {_2ecc_id[1]});
        auto path = construct_path(bridge_tree, p, {_2ecc_id[n]});
        set<pair<int, int>> on_path;
        for(int i = 1; i < path.size(); i++) {
            on_path.insert({path[i - 1], path[i]});
        }
        bool increase = false;
        for(int ii = 0; ii < sp_dag.edges.size(); ii += 2) {
            auto [u, v, w, i, dw] = sp_dag.edges[ii];
            increase |= cut_edge[ii]
                and on_path.count({_2ecc_id[u], _2ecc_id[v]})
                and ds[u] + w + dw + dt[v] >= ds[n] + delta;
        }
        if(increase) {
            ans = ds[n] + delta;
        }
    }
    cout << ans << endl;
    return 0;
}

Compilation message

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:142:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<wedge<long long int>, std::allocator<wedge<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         for(int ii = 0; ii < g.edges.size(); ii += 2) {
      |                         ~~~^~~~~~~~~~~~~~~~
Aesthetic.cpp:159:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |         for(int i = 1; i < path.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
Aesthetic.cpp:163:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<wedge<long long int>, std::allocator<wedge<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         for(int ii = 0; ii < sp_dag.edges.size(); ii += 2) {
      |                         ~~~^~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp: In instantiation of 'std::pair<std::vector<int>, std::vector<std::vector<int> > > find_2eccs(graph<false, TEdge, Index>&) [with TEdge = wedge<long long int>; bool Index = true]':
Aesthetic.cpp:154:52:   required from here
Aesthetic.cpp:91:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int u = Index; u < g.adj.size(); u++) if(not vis[u]) {
      |                        ~~^~~~~~~~~~~~~~
Aesthetic.cpp: In instantiation of 'std::pair<std::vector<int>, graph<false, TEdge, Index> > build_bridge_tree(graph<false, TEdge, Index>&, const std::vector<int>&, const std::vector<std::vector<int> >&) [with TEdge = wedge<long long int>; bool Index = true]':
Aesthetic.cpp:155:82:   required from here
Aesthetic.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i = 0; i < _2eccs.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
Aesthetic.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<wedge<long long int>, std::allocator<wedge<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int e = 0; e < g.edges.size(); e++) {
      |                    ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 904 ms 79104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 925 ms 80740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 67004 KB Output is correct
2 Correct 957 ms 120876 KB Output is correct
3 Correct 1436 ms 98576 KB Output is correct
4 Correct 1486 ms 98032 KB Output is correct
5 Correct 1527 ms 97556 KB Output is correct
6 Correct 1463 ms 98260 KB Output is correct
7 Correct 1426 ms 98152 KB Output is correct
8 Correct 1374 ms 97920 KB Output is correct
9 Correct 1449 ms 98128 KB Output is correct
10 Correct 1560 ms 97888 KB Output is correct
11 Correct 1494 ms 97848 KB Output is correct
12 Correct 756 ms 62720 KB Output is correct
13 Correct 1388 ms 98348 KB Output is correct
14 Correct 678 ms 124700 KB Output is correct
15 Correct 716 ms 123944 KB Output is correct
16 Correct 744 ms 64184 KB Output is correct
17 Correct 746 ms 64604 KB Output is correct
18 Correct 733 ms 61740 KB Output is correct
19 Correct 921 ms 108580 KB Output is correct
20 Correct 919 ms 108624 KB Output is correct
21 Correct 895 ms 114252 KB Output is correct
22 Correct 900 ms 110884 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 847 ms 67004 KB Output is correct
2 Correct 957 ms 120876 KB Output is correct
3 Correct 1436 ms 98576 KB Output is correct
4 Correct 1486 ms 98032 KB Output is correct
5 Correct 1527 ms 97556 KB Output is correct
6 Correct 1463 ms 98260 KB Output is correct
7 Correct 1426 ms 98152 KB Output is correct
8 Correct 1374 ms 97920 KB Output is correct
9 Correct 1449 ms 98128 KB Output is correct
10 Correct 1560 ms 97888 KB Output is correct
11 Correct 1494 ms 97848 KB Output is correct
12 Correct 756 ms 62720 KB Output is correct
13 Correct 1388 ms 98348 KB Output is correct
14 Correct 678 ms 124700 KB Output is correct
15 Correct 716 ms 123944 KB Output is correct
16 Correct 744 ms 64184 KB Output is correct
17 Correct 746 ms 64604 KB Output is correct
18 Correct 733 ms 61740 KB Output is correct
19 Correct 921 ms 108580 KB Output is correct
20 Correct 919 ms 108624 KB Output is correct
21 Correct 895 ms 114252 KB Output is correct
22 Correct 900 ms 110884 KB Output is correct
23 Correct 778 ms 62772 KB Output is correct
24 Correct 627 ms 84636 KB Output is correct
25 Correct 724 ms 77524 KB Output is correct
26 Correct 700 ms 74996 KB Output is correct
27 Correct 671 ms 74644 KB Output is correct
28 Correct 753 ms 77660 KB Output is correct
29 Correct 647 ms 75344 KB Output is correct
30 Correct 715 ms 75784 KB Output is correct
31 Correct 751 ms 76412 KB Output is correct
32 Correct 720 ms 75208 KB Output is correct
33 Correct 784 ms 77008 KB Output is correct
34 Correct 751 ms 62024 KB Output is correct
35 Correct 710 ms 75236 KB Output is correct
36 Correct 628 ms 111972 KB Output is correct
37 Incorrect 646 ms 111836 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -