oj.uz

Submission #603467

# Submission time Handle Problem Language Result Execution time Memory
603467 2022-07-24T07:23:47 Z verngutz Aesthetic (NOI20_aesthetic) C++17
38 / 100
 1621 ms 124560 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++) {
            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++) {
      |                         ~~~^~~~~~~~~~~~~~~~~~~~~
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 212 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1141 ms 80736 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 934 ms 67108 KB Output is correct
2 Correct 1049 ms 120952 KB Output is correct
3 Correct 1455 ms 98360 KB Output is correct
4 Correct 1412 ms 98112 KB Output is correct
5 Correct 1442 ms 97672 KB Output is correct
6 Correct 1424 ms 98200 KB Output is correct
7 Correct 1460 ms 98088 KB Output is correct
8 Correct 1480 ms 97880 KB Output is correct
9 Correct 1451 ms 97992 KB Output is correct
10 Correct 1621 ms 97972 KB Output is correct
11 Correct 1518 ms 97900 KB Output is correct
12 Correct 869 ms 62616 KB Output is correct
13 Correct 1596 ms 98308 KB Output is correct
14 Correct 788 ms 124560 KB Output is correct
15 Correct 875 ms 123960 KB Output is correct
16 Correct 798 ms 64164 KB Output is correct
17 Correct 843 ms 64636 KB Output is correct
18 Correct 840 ms 61688 KB Output is correct
19 Correct 1071 ms 108644 KB Output is correct
20 Correct 1076 ms 108612 KB Output is correct
21 Correct 1047 ms 114276 KB Output is correct
22 Correct 939 ms 110844 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 67108 KB Output is correct
2 Correct 1049 ms 120952 KB Output is correct
3 Correct 1455 ms 98360 KB Output is correct
4 Correct 1412 ms 98112 KB Output is correct
5 Correct 1442 ms 97672 KB Output is correct
6 Correct 1424 ms 98200 KB Output is correct
7 Correct 1460 ms 98088 KB Output is correct
8 Correct 1480 ms 97880 KB Output is correct
9 Correct 1451 ms 97992 KB Output is correct
10 Correct 1621 ms 97972 KB Output is correct
11 Correct 1518 ms 97900 KB Output is correct
12 Correct 869 ms 62616 KB Output is correct
13 Correct 1596 ms 98308 KB Output is correct
14 Correct 788 ms 124560 KB Output is correct
15 Correct 875 ms 123960 KB Output is correct
16 Correct 798 ms 64164 KB Output is correct
17 Correct 843 ms 64636 KB Output is correct
18 Correct 840 ms 61688 KB Output is correct
19 Correct 1071 ms 108644 KB Output is correct
20 Correct 1076 ms 108612 KB Output is correct
21 Correct 1047 ms 114276 KB Output is correct
22 Correct 939 ms 110844 KB Output is correct
23 Correct 851 ms 62868 KB Output is correct
24 Correct 666 ms 84572 KB Output is correct
25 Correct 810 ms 77712 KB Output is correct
26 Correct 700 ms 75092 KB Output is correct
27 Correct 733 ms 74784 KB Output is correct
28 Correct 885 ms 77600 KB Output is correct
29 Correct 731 ms 75312 KB Output is correct
30 Correct 774 ms 75592 KB Output is correct
31 Correct 772 ms 76264 KB Output is correct
32 Correct 763 ms 75096 KB Output is correct
33 Correct 860 ms 76984 KB Output is correct
34 Correct 880 ms 61840 KB Output is correct
35 Correct 859 ms 75252 KB Output is correct
36 Correct 761 ms 111784 KB Output is correct
37 Correct 793 ms 111792 KB Output is correct
38 Correct 812 ms 66716 KB Output is correct
39 Correct 817 ms 65620 KB Output is correct
40 Correct 831 ms 67068 KB Output is correct
41 Correct 629 ms 88928 KB Output is correct
42 Correct 603 ms 87760 KB Output is correct
43 Correct 636 ms 87840 KB Output is correct
44 Correct 656 ms 88248 KB Output is correct

Subtask #7
0 / 27.0

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