oj.uz

Submission #603480

# Submission time Handle Problem Language Result Execution time Memory
603480 2022-07-24T07:28:48 Z verngutz Aesthetic (NOI20_aesthetic) C++17
58 / 100
 2000 ms 111600 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;
}
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]});
        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++) {
            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:152: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]
  152 |         for(int ii = 0; ii < g.edges.size(); ii += 2) {
      |                         ~~~^~~~~~~~~~~~~~~~
Aesthetic.cpp:163:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         for(int i = 1; i < path.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
Aesthetic.cpp:167: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]
  167 |         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:158: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:159: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 340 KB Output is correct
2 Correct 1 ms 316 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 316 KB Output is correct
8 Correct 1 ms 320 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 316 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 316 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 6 ms 836 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 9 ms 952 KB Output is correct
12 Correct 12 ms 852 KB Output is correct
13 Correct 5 ms 848 KB Output is correct
14 Correct 5 ms 928 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 1699 ms 83832 KB Output is correct
2 Correct 1635 ms 91740 KB Output is correct
3 Correct 1718 ms 89956 KB Output is correct
4 Correct 1760 ms 90140 KB Output is correct
5 Correct 1708 ms 90392 KB Output is correct
6 Correct 1742 ms 91920 KB Output is correct
7 Correct 1724 ms 91616 KB Output is correct
8 Correct 1696 ms 92136 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1730 ms 85456 KB Output is correct
2 Correct 1715 ms 91056 KB Output is correct
3 Correct 1709 ms 90520 KB Output is correct
4 Correct 1702 ms 91820 KB Output is correct
5 Correct 1844 ms 90580 KB Output is correct
6 Execution timed out 2095 ms 90536 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 63692 KB Output is correct
2 Correct 225 ms 76448 KB Output is correct
3 Correct 428 ms 71416 KB Output is correct
4 Correct 360 ms 71300 KB Output is correct
5 Correct 364 ms 71280 KB Output is correct
6 Correct 373 ms 71456 KB Output is correct
7 Correct 399 ms 71700 KB Output is correct
8 Correct 351 ms 71680 KB Output is correct
9 Correct 368 ms 71616 KB Output is correct
10 Correct 319 ms 72052 KB Output is correct
11 Correct 328 ms 71616 KB Output is correct
12 Correct 477 ms 63788 KB Output is correct
13 Correct 370 ms 71524 KB Output is correct
14 Correct 210 ms 98616 KB Output is correct
15 Correct 208 ms 98744 KB Output is correct
16 Correct 498 ms 62848 KB Output is correct
17 Correct 450 ms 60272 KB Output is correct
18 Correct 453 ms 62368 KB Output is correct
19 Correct 219 ms 76868 KB Output is correct
20 Correct 227 ms 76884 KB Output is correct
21 Correct 214 ms 76832 KB Output is correct
22 Correct 225 ms 76712 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 63692 KB Output is correct
2 Correct 225 ms 76448 KB Output is correct
3 Correct 428 ms 71416 KB Output is correct
4 Correct 360 ms 71300 KB Output is correct
5 Correct 364 ms 71280 KB Output is correct
6 Correct 373 ms 71456 KB Output is correct
7 Correct 399 ms 71700 KB Output is correct
8 Correct 351 ms 71680 KB Output is correct
9 Correct 368 ms 71616 KB Output is correct
10 Correct 319 ms 72052 KB Output is correct
11 Correct 328 ms 71616 KB Output is correct
12 Correct 477 ms 63788 KB Output is correct
13 Correct 370 ms 71524 KB Output is correct
14 Correct 210 ms 98616 KB Output is correct
15 Correct 208 ms 98744 KB Output is correct
16 Correct 498 ms 62848 KB Output is correct
17 Correct 450 ms 60272 KB Output is correct
18 Correct 453 ms 62368 KB Output is correct
19 Correct 219 ms 76868 KB Output is correct
20 Correct 227 ms 76884 KB Output is correct
21 Correct 214 ms 76832 KB Output is correct
22 Correct 225 ms 76712 KB Output is correct
23 Correct 618 ms 65996 KB Output is correct
24 Correct 408 ms 88780 KB Output is correct
25 Correct 300 ms 46656 KB Output is correct
26 Correct 307 ms 44748 KB Output is correct
27 Correct 304 ms 45308 KB Output is correct
28 Correct 334 ms 47240 KB Output is correct
29 Correct 286 ms 44796 KB Output is correct
30 Correct 295 ms 46724 KB Output is correct
31 Correct 270 ms 46508 KB Output is correct
32 Correct 303 ms 45536 KB Output is correct
33 Correct 332 ms 47252 KB Output is correct
34 Correct 576 ms 64984 KB Output is correct
35 Correct 298 ms 46232 KB Output is correct
36 Correct 266 ms 111576 KB Output is correct
37 Correct 265 ms 111600 KB Output is correct
38 Correct 580 ms 63516 KB Output is correct
39 Correct 575 ms 62292 KB Output is correct
40 Correct 629 ms 63920 KB Output is correct
41 Correct 401 ms 86904 KB Output is correct
42 Correct 424 ms 88708 KB Output is correct
43 Correct 431 ms 86976 KB Output is correct
44 Correct 414 ms 86816 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 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 316 KB Output is correct
8 Correct 1 ms 320 KB Output is correct
9 Correct 6 ms 836 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 9 ms 952 KB Output is correct
12 Correct 12 ms 852 KB Output is correct
13 Correct 5 ms 848 KB Output is correct
14 Correct 5 ms 928 KB Output is correct
15 Correct 5 ms 852 KB Output is correct
16 Correct 4 ms 856 KB Output is correct
17 Correct 1699 ms 83832 KB Output is correct
18 Correct 1635 ms 91740 KB Output is correct
19 Correct 1718 ms 89956 KB Output is correct
20 Correct 1760 ms 90140 KB Output is correct
21 Correct 1708 ms 90392 KB Output is correct
22 Correct 1742 ms 91920 KB Output is correct
23 Correct 1724 ms 91616 KB Output is correct
24 Correct 1696 ms 92136 KB Output is correct
25 Correct 1730 ms 85456 KB Output is correct
26 Correct 1715 ms 91056 KB Output is correct
27 Correct 1709 ms 90520 KB Output is correct
28 Correct 1702 ms 91820 KB Output is correct
29 Correct 1844 ms 90580 KB Output is correct
30 Execution timed out 2095 ms 90536 KB Time limit exceeded
31 Halted 0 ms 0 KB -