oj.uz

Submission #603039

# Submission time Handle Problem Language Result Execution time Memory
603039 2022-07-23T14:31:04 Z verngutz Aesthetic (NOI20_aesthetic) C++17
51 / 100
 2000 ms 80436 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 <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)};
}
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});
    if(all_of(g.edges.begin(), g.edges.end(), [](const wedge<ll>& e) { return e.w == 1; }) or m <= n) {
        graph<0, wedge<ll>, 1> sp_dag(n);
        for(auto [i, u, v, w, dw] : g.edges) {
            if(ds[u] + w + dt[v] == ds[n]) {
                sp_dag.add_edge({i, u, v, w, dw});
            }
        }
        auto [cut_edge, _2eccs] = find_2eccs(sp_dag);
        ll ans = ds[n];
        for(int ii = 0; ii < sp_dag.edges.size(); ii += 2) {
            auto [i, u, v, w, dw] = sp_dag.edges[ii];
            if(cut_edge[ii]) {
                ans = max(ans, ds[u] + w + dw + dt[v]);
            }
        }
        cout << ans << endl;
    } else {
        ll max_replace = 0;
        ll ans = ds[n];
        for(int i = m - 1; i >= 0; i--) {
            g.edges[2 * i].w += max_replace;
            g.edges[2 * i + 1].w += max_replace;
            ans = max(ans, sssp(g, {1}).first[n]);
            g.edges[2 * i].w -= max_replace;
            g.edges[2 * i + 1].w -= max_replace;
            max_replace = max(max_replace, g.edges[2 * i].w);
        }
        cout << ans << endl;
    }
    return 0;
}

Compilation message

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:117: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]
  117 |         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:115:52:   required from here
Aesthetic.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int u = Index; u < g.adj.size(); u++) if(not vis[u]) {
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 331 ms 608 KB Output is correct
10 Correct 335 ms 608 KB Output is correct
11 Correct 235 ms 596 KB Output is correct
12 Correct 264 ms 564 KB Output is correct
13 Correct 139 ms 544 KB Output is correct
14 Correct 149 ms 468 KB Output is correct
15 Correct 186 ms 556 KB Output is correct
16 Correct 146 ms 560 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 72760 KB Output is correct
2 Correct 502 ms 78400 KB Output is correct
3 Correct 485 ms 77800 KB Output is correct
4 Correct 486 ms 77816 KB Output is correct
5 Correct 557 ms 78372 KB Output is correct
6 Correct 542 ms 79288 KB Output is correct
7 Correct 542 ms 78980 KB Output is correct
8 Correct 538 ms 79432 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 74068 KB Output is correct
2 Correct 538 ms 78468 KB Output is correct
3 Correct 537 ms 78080 KB Output is correct
4 Correct 543 ms 79080 KB Output is correct
5 Correct 552 ms 78324 KB Output is correct
6 Correct 512 ms 78280 KB Output is correct
7 Correct 497 ms 78248 KB Output is correct
8 Correct 498 ms 78784 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 54352 KB Output is correct
2 Correct 209 ms 66916 KB Output is correct
3 Correct 320 ms 73968 KB Output is correct
4 Correct 363 ms 73792 KB Output is correct
5 Correct 321 ms 73728 KB Output is correct
6 Correct 377 ms 73876 KB Output is correct
7 Correct 344 ms 74156 KB Output is correct
8 Correct 371 ms 74184 KB Output is correct
9 Correct 364 ms 74056 KB Output is correct
10 Correct 391 ms 74528 KB Output is correct
11 Correct 355 ms 74088 KB Output is correct
12 Correct 470 ms 57044 KB Output is correct
13 Correct 353 ms 73968 KB Output is correct
14 Correct 168 ms 80304 KB Output is correct
15 Correct 175 ms 80436 KB Output is correct
16 Correct 501 ms 56368 KB Output is correct
17 Correct 431 ms 54828 KB Output is correct
18 Correct 529 ms 55828 KB Output is correct
19 Correct 229 ms 67072 KB Output is correct
20 Correct 235 ms 67080 KB Output is correct
21 Correct 280 ms 67072 KB Output is correct
22 Correct 221 ms 67016 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 54352 KB Output is correct
2 Correct 209 ms 66916 KB Output is correct
3 Correct 320 ms 73968 KB Output is correct
4 Correct 363 ms 73792 KB Output is correct
5 Correct 321 ms 73728 KB Output is correct
6 Correct 377 ms 73876 KB Output is correct
7 Correct 344 ms 74156 KB Output is correct
8 Correct 371 ms 74184 KB Output is correct
9 Correct 364 ms 74056 KB Output is correct
10 Correct 391 ms 74528 KB Output is correct
11 Correct 355 ms 74088 KB Output is correct
12 Correct 470 ms 57044 KB Output is correct
13 Correct 353 ms 73968 KB Output is correct
14 Correct 168 ms 80304 KB Output is correct
15 Correct 175 ms 80436 KB Output is correct
16 Correct 501 ms 56368 KB Output is correct
17 Correct 431 ms 54828 KB Output is correct
18 Correct 529 ms 55828 KB Output is correct
19 Correct 229 ms 67072 KB Output is correct
20 Correct 235 ms 67080 KB Output is correct
21 Correct 280 ms 67072 KB Output is correct
22 Correct 221 ms 67016 KB Output is correct
23 Execution timed out 2084 ms 46588 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 331 ms 608 KB Output is correct
10 Correct 335 ms 608 KB Output is correct
11 Correct 235 ms 596 KB Output is correct
12 Correct 264 ms 564 KB Output is correct
13 Correct 139 ms 544 KB Output is correct
14 Correct 149 ms 468 KB Output is correct
15 Correct 186 ms 556 KB Output is correct
16 Correct 146 ms 560 KB Output is correct
17 Correct 517 ms 72760 KB Output is correct
18 Correct 502 ms 78400 KB Output is correct
19 Correct 485 ms 77800 KB Output is correct
20 Correct 486 ms 77816 KB Output is correct
21 Correct 557 ms 78372 KB Output is correct
22 Correct 542 ms 79288 KB Output is correct
23 Correct 542 ms 78980 KB Output is correct
24 Correct 538 ms 79432 KB Output is correct
25 Correct 524 ms 74068 KB Output is correct
26 Correct 538 ms 78468 KB Output is correct
27 Correct 537 ms 78080 KB Output is correct
28 Correct 543 ms 79080 KB Output is correct
29 Correct 552 ms 78324 KB Output is correct
30 Correct 512 ms 78280 KB Output is correct
31 Correct 497 ms 78248 KB Output is correct
32 Correct 498 ms 78784 KB Output is correct
33 Correct 506 ms 54352 KB Output is correct
34 Correct 209 ms 66916 KB Output is correct
35 Correct 320 ms 73968 KB Output is correct
36 Correct 363 ms 73792 KB Output is correct
37 Correct 321 ms 73728 KB Output is correct
38 Correct 377 ms 73876 KB Output is correct
39 Correct 344 ms 74156 KB Output is correct
40 Correct 371 ms 74184 KB Output is correct
41 Correct 364 ms 74056 KB Output is correct
42 Correct 391 ms 74528 KB Output is correct
43 Correct 355 ms 74088 KB Output is correct
44 Correct 470 ms 57044 KB Output is correct
45 Correct 353 ms 73968 KB Output is correct
46 Correct 168 ms 80304 KB Output is correct
47 Correct 175 ms 80436 KB Output is correct
48 Correct 501 ms 56368 KB Output is correct
49 Correct 431 ms 54828 KB Output is correct
50 Correct 529 ms 55828 KB Output is correct
51 Correct 229 ms 67072 KB Output is correct
52 Correct 235 ms 67080 KB Output is correct
53 Correct 280 ms 67072 KB Output is correct
54 Correct 221 ms 67016 KB Output is correct
55 Execution timed out 2084 ms 46588 KB Time limit exceeded
56 Halted 0 ms 0 KB -