oj.uz

Submission #603428

# Submission time Handle Problem Language Result Execution time Memory
603428 2022-07-24T06:47:00 Z verngutz Aesthetic (NOI20_aesthetic) C++17
16 / 100
 1950 ms 129756 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 i, u, v; T w, dw;
    wedge reverse() const { return {i, v, u, w, 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)};
}
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({i, u, v, 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});
    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 [i, u, v, w, 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({i, u, v, w, dw});
                } else {
                    sp_dag.add_edge({i, v, u, w, dw});
                }
            }
        }
        auto [d, p] = sssp(sp_dag, {1});
        auto path = construct_path(sp_dag, p, n);
        set<pair<int, int>> on_path;
        for(int i = 1; i < path.size(); i++) {
            on_path.insert({path[i - 1], path[i]});
        }
        auto [cut_edge, _2eccs] = find_2eccs(sp_dag);
        bool increase = false;
        for(int ii = 0; ii < sp_dag.edges.size(); ii += 2) {
            auto [i, u, v, w, dw] = sp_dag.edges[ii];
            increase |= cut_edge[ii] and on_path.count({u, 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:121: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]
  121 |         for(int ii = 0; ii < g.edges.size(); ii += 2) {
      |                         ~~~^~~~~~~~~~~~~~~~
Aesthetic.cpp:136:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |         for(int i = 1; i < path.size(); i++) {
      |                        ~~^~~~~~~~~~~~~
Aesthetic.cpp:141: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]
  141 |         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:139:52:   required from here
Aesthetic.cpp:90:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int u = Index; u < g.adj.size(); u++) if(not vis[u]) {
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 0 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 868 ms 75656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 832 ms 77344 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 821 ms 62464 KB Output is correct
2 Correct 999 ms 103864 KB Output is correct
3 Correct 1701 ms 97644 KB Output is correct
4 Correct 1761 ms 98188 KB Output is correct
5 Correct 1726 ms 98164 KB Output is correct
6 Correct 1749 ms 98396 KB Output is correct
7 Correct 1950 ms 97832 KB Output is correct
8 Correct 1716 ms 98476 KB Output is correct
9 Correct 1723 ms 97512 KB Output is correct
10 Correct 1794 ms 98996 KB Output is correct
11 Correct 1714 ms 98396 KB Output is correct
12 Correct 713 ms 57460 KB Output is correct
13 Correct 1794 ms 98480 KB Output is correct
14 Correct 871 ms 129756 KB Output is correct
15 Correct 911 ms 129324 KB Output is correct
16 Correct 781 ms 59376 KB Output is correct
17 Correct 799 ms 61752 KB Output is correct
18 Correct 676 ms 58268 KB Output is correct
19 Correct 1079 ms 106168 KB Output is correct
20 Correct 1057 ms 106500 KB Output is correct
21 Correct 1087 ms 105868 KB Output is correct
22 Correct 1034 ms 105972 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 821 ms 62464 KB Output is correct
2 Correct 999 ms 103864 KB Output is correct
3 Correct 1701 ms 97644 KB Output is correct
4 Correct 1761 ms 98188 KB Output is correct
5 Correct 1726 ms 98164 KB Output is correct
6 Correct 1749 ms 98396 KB Output is correct
7 Correct 1950 ms 97832 KB Output is correct
8 Correct 1716 ms 98476 KB Output is correct
9 Correct 1723 ms 97512 KB Output is correct
10 Correct 1794 ms 98996 KB Output is correct
11 Correct 1714 ms 98396 KB Output is correct
12 Correct 713 ms 57460 KB Output is correct
13 Correct 1794 ms 98480 KB Output is correct
14 Correct 871 ms 129756 KB Output is correct
15 Correct 911 ms 129324 KB Output is correct
16 Correct 781 ms 59376 KB Output is correct
17 Correct 799 ms 61752 KB Output is correct
18 Correct 676 ms 58268 KB Output is correct
19 Correct 1079 ms 106168 KB Output is correct
20 Correct 1057 ms 106500 KB Output is correct
21 Correct 1087 ms 105868 KB Output is correct
22 Correct 1034 ms 105972 KB Output is correct
23 Correct 766 ms 56144 KB Output is correct
24 Correct 619 ms 75324 KB Output is correct
25 Correct 989 ms 80796 KB Output is correct
26 Correct 817 ms 79260 KB Output is correct
27 Correct 791 ms 77808 KB Output is correct
28 Correct 954 ms 81696 KB Output is correct
29 Correct 811 ms 77692 KB Output is correct
30 Correct 862 ms 77780 KB Output is correct
31 Correct 839 ms 79556 KB Output is correct
32 Correct 865 ms 79340 KB Output is correct
33 Correct 917 ms 80748 KB Output is correct
34 Correct 754 ms 61968 KB Output is correct
35 Correct 873 ms 79404 KB Output is correct
36 Correct 1128 ms 117892 KB Output is correct
37 Incorrect 898 ms 118524 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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