oj.uz

Submission #603519

# Submission time Handle Problem Language Result Execution time Memory
603519 2022-07-24T07:45:10 Z verngutz Aesthetic (NOI20_aesthetic) C++17
100 / 100
 1847 ms 117656 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);
}
template <typename T, typename Can> T bsearch(T L, T R, const Can& can, bool left_feasible = true) {
    static_assert(is_convertible<decltype(can), function<bool(T)>>::value);
    T& feasible = left_feasible ? L : R;
    T& infeasible = left_feasible ? R : L;
    while(R - L > 1) {
        T M = L + (R - L) / 2;
        (can(M) ? feasible : infeasible) = M;
    }
    return feasible;
}
const int MAX_N = 300'000;
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);
    int max_w = 0;
    for(int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g.add_edge({u, v, w, i});
        max_w = max(max_w, w);
    }
    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});
    cout << ds[n] + bsearch(0, max_w + 1, [&, &ds=ds, &dt=dt](int 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];
            if(min(ds[u] + w + dt[v], ds[v] + w + dt[u]) < ds[n] + delta) {
                sp_dag.add_edge({u, v, 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]});
        auto pair_hash = [](const pair<int, int>& p) {
            return hash<ll>()(ll(p.first) * (MAX_N + 1) + p.second);
        };
        unordered_set<pair<int, int>, decltype(pair_hash)> on_path(0, pair_hash);
        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++) {
            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;
        }
        return increase;
    }) << endl;
    return 0;
}

Compilation message

Aesthetic.cpp: In lambda function:
Aesthetic.cpp:153: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]
  153 |         for(int ii = 0; ii < g.edges.size(); ii += 2) {
      |                         ~~~^~~~~~~~~~~~~~~~
Aesthetic.cpp:167:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |         for(int i = 1; i < path.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
Aesthetic.cpp:171: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]
  171 |         for(int ii = 0; ii < sp_dag.edges.size(); ii++) {
      |                         ~~~^~~~~~~~~~~~~~~~~~~~~
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:159: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:160: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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 280 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 212 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 280 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 8 ms 756 KB Output is correct
10 Correct 5 ms 724 KB Output is correct
11 Correct 10 ms 884 KB Output is correct
12 Correct 10 ms 824 KB Output is correct
13 Correct 5 ms 856 KB Output is correct
14 Correct 5 ms 852 KB Output is correct
15 Correct 5 ms 852 KB Output is correct
16 Correct 4 ms 856 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1735 ms 79240 KB Output is correct
2 Correct 1703 ms 79548 KB Output is correct
3 Correct 1724 ms 78764 KB Output is correct
4 Correct 1667 ms 78972 KB Output is correct
5 Correct 1711 ms 79320 KB Output is correct
6 Correct 1704 ms 80648 KB Output is correct
7 Correct 1785 ms 80236 KB Output is correct
8 Correct 1706 ms 80860 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1733 ms 80816 KB Output is correct
2 Correct 1713 ms 79924 KB Output is correct
3 Correct 1682 ms 79368 KB Output is correct
4 Correct 1672 ms 80368 KB Output is correct
5 Correct 1699 ms 79256 KB Output is correct
6 Correct 1601 ms 79348 KB Output is correct
7 Correct 1674 ms 79428 KB Output is correct
8 Correct 1746 ms 80016 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 60348 KB Output is correct
2 Correct 226 ms 72424 KB Output is correct
3 Correct 308 ms 69860 KB Output is correct
4 Correct 347 ms 69720 KB Output is correct
5 Correct 335 ms 69752 KB Output is correct
6 Correct 363 ms 70068 KB Output is correct
7 Correct 315 ms 70220 KB Output is correct
8 Correct 329 ms 70160 KB Output is correct
9 Correct 348 ms 70068 KB Output is correct
10 Correct 307 ms 70572 KB Output is correct
11 Correct 343 ms 70060 KB Output is correct
12 Correct 439 ms 60728 KB Output is correct
13 Correct 357 ms 69968 KB Output is correct
14 Correct 175 ms 95512 KB Output is correct
15 Correct 187 ms 95676 KB Output is correct
16 Correct 446 ms 59732 KB Output is correct
17 Correct 449 ms 57328 KB Output is correct
18 Correct 492 ms 59192 KB Output is correct
19 Correct 202 ms 72776 KB Output is correct
20 Correct 214 ms 72860 KB Output is correct
21 Correct 227 ms 72688 KB Output is correct
22 Correct 208 ms 72652 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 60348 KB Output is correct
2 Correct 226 ms 72424 KB Output is correct
3 Correct 308 ms 69860 KB Output is correct
4 Correct 347 ms 69720 KB Output is correct
5 Correct 335 ms 69752 KB Output is correct
6 Correct 363 ms 70068 KB Output is correct
7 Correct 315 ms 70220 KB Output is correct
8 Correct 329 ms 70160 KB Output is correct
9 Correct 348 ms 70068 KB Output is correct
10 Correct 307 ms 70572 KB Output is correct
11 Correct 343 ms 70060 KB Output is correct
12 Correct 439 ms 60728 KB Output is correct
13 Correct 357 ms 69968 KB Output is correct
14 Correct 175 ms 95512 KB Output is correct
15 Correct 187 ms 95676 KB Output is correct
16 Correct 446 ms 59732 KB Output is correct
17 Correct 449 ms 57328 KB Output is correct
18 Correct 492 ms 59192 KB Output is correct
19 Correct 202 ms 72776 KB Output is correct
20 Correct 214 ms 72860 KB Output is correct
21 Correct 227 ms 72688 KB Output is correct
22 Correct 208 ms 72652 KB Output is correct
23 Correct 609 ms 60880 KB Output is correct
24 Correct 431 ms 82804 KB Output is correct
25 Correct 276 ms 45208 KB Output is correct
26 Correct 267 ms 43348 KB Output is correct
27 Correct 279 ms 43800 KB Output is correct
28 Correct 309 ms 45668 KB Output is correct
29 Correct 297 ms 43204 KB Output is correct
30 Correct 278 ms 45180 KB Output is correct
31 Correct 289 ms 44864 KB Output is correct
32 Correct 276 ms 44008 KB Output is correct
33 Correct 291 ms 45676 KB Output is correct
34 Correct 589 ms 59804 KB Output is correct
35 Correct 278 ms 44816 KB Output is correct
36 Correct 225 ms 109144 KB Output is correct
37 Correct 249 ms 109100 KB Output is correct
38 Correct 555 ms 60424 KB Output is correct
39 Correct 575 ms 59732 KB Output is correct
40 Correct 569 ms 60772 KB Output is correct
41 Correct 440 ms 82748 KB Output is correct
42 Correct 460 ms 81720 KB Output is correct
43 Correct 426 ms 82944 KB Output is correct
44 Correct 415 ms 82828 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 280 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 8 ms 756 KB Output is correct
10 Correct 5 ms 724 KB Output is correct
11 Correct 10 ms 884 KB Output is correct
12 Correct 10 ms 824 KB Output is correct
13 Correct 5 ms 856 KB Output is correct
14 Correct 5 ms 852 KB Output is correct
15 Correct 5 ms 852 KB Output is correct
16 Correct 4 ms 856 KB Output is correct
17 Correct 1735 ms 79240 KB Output is correct
18 Correct 1703 ms 79548 KB Output is correct
19 Correct 1724 ms 78764 KB Output is correct
20 Correct 1667 ms 78972 KB Output is correct
21 Correct 1711 ms 79320 KB Output is correct
22 Correct 1704 ms 80648 KB Output is correct
23 Correct 1785 ms 80236 KB Output is correct
24 Correct 1706 ms 80860 KB Output is correct
25 Correct 1733 ms 80816 KB Output is correct
26 Correct 1713 ms 79924 KB Output is correct
27 Correct 1682 ms 79368 KB Output is correct
28 Correct 1672 ms 80368 KB Output is correct
29 Correct 1699 ms 79256 KB Output is correct
30 Correct 1601 ms 79348 KB Output is correct
31 Correct 1674 ms 79428 KB Output is correct
32 Correct 1746 ms 80016 KB Output is correct
33 Correct 462 ms 60348 KB Output is correct
34 Correct 226 ms 72424 KB Output is correct
35 Correct 308 ms 69860 KB Output is correct
36 Correct 347 ms 69720 KB Output is correct
37 Correct 335 ms 69752 KB Output is correct
38 Correct 363 ms 70068 KB Output is correct
39 Correct 315 ms 70220 KB Output is correct
40 Correct 329 ms 70160 KB Output is correct
41 Correct 348 ms 70068 KB Output is correct
42 Correct 307 ms 70572 KB Output is correct
43 Correct 343 ms 70060 KB Output is correct
44 Correct 439 ms 60728 KB Output is correct
45 Correct 357 ms 69968 KB Output is correct
46 Correct 175 ms 95512 KB Output is correct
47 Correct 187 ms 95676 KB Output is correct
48 Correct 446 ms 59732 KB Output is correct
49 Correct 449 ms 57328 KB Output is correct
50 Correct 492 ms 59192 KB Output is correct
51 Correct 202 ms 72776 KB Output is correct
52 Correct 214 ms 72860 KB Output is correct
53 Correct 227 ms 72688 KB Output is correct
54 Correct 208 ms 72652 KB Output is correct
55 Correct 609 ms 60880 KB Output is correct
56 Correct 431 ms 82804 KB Output is correct
57 Correct 276 ms 45208 KB Output is correct
58 Correct 267 ms 43348 KB Output is correct
59 Correct 279 ms 43800 KB Output is correct
60 Correct 309 ms 45668 KB Output is correct
61 Correct 297 ms 43204 KB Output is correct
62 Correct 278 ms 45180 KB Output is correct
63 Correct 289 ms 44864 KB Output is correct
64 Correct 276 ms 44008 KB Output is correct
65 Correct 291 ms 45676 KB Output is correct
66 Correct 589 ms 59804 KB Output is correct
67 Correct 278 ms 44816 KB Output is correct
68 Correct 225 ms 109144 KB Output is correct
69 Correct 249 ms 109100 KB Output is correct
70 Correct 555 ms 60424 KB Output is correct
71 Correct 575 ms 59732 KB Output is correct
72 Correct 569 ms 60772 KB Output is correct
73 Correct 440 ms 82748 KB Output is correct
74 Correct 460 ms 81720 KB Output is correct
75 Correct 426 ms 82944 KB Output is correct
76 Correct 415 ms 82828 KB Output is correct
77 Correct 1513 ms 63552 KB Output is correct
78 Correct 1743 ms 84144 KB Output is correct
79 Correct 992 ms 97284 KB Output is correct
80 Correct 999 ms 97160 KB Output is correct
81 Correct 999 ms 97156 KB Output is correct
82 Correct 1066 ms 97680 KB Output is correct
83 Correct 1074 ms 96456 KB Output is correct
84 Correct 1010 ms 97748 KB Output is correct
85 Correct 946 ms 97180 KB Output is correct
86 Correct 1010 ms 96188 KB Output is correct
87 Correct 1044 ms 97704 KB Output is correct
88 Correct 1526 ms 62712 KB Output is correct
89 Correct 1035 ms 97704 KB Output is correct
90 Correct 909 ms 117656 KB Output is correct
91 Correct 952 ms 112988 KB Output is correct
92 Correct 1513 ms 62408 KB Output is correct
93 Correct 1455 ms 62524 KB Output is correct
94 Correct 1446 ms 61880 KB Output is correct
95 Correct 1696 ms 85076 KB Output is correct
96 Correct 1699 ms 86004 KB Output is correct
97 Correct 1828 ms 84224 KB Output is correct
98 Correct 1847 ms 85012 KB Output is correct