oj.uz

Submission #603015

# Submission time Handle Problem Language Result Execution time Memory
603015 2022-07-23T14:21:54 Z verngutz Aesthetic (NOI20_aesthetic) C++17
36 / 100
 2000 ms 74072 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;
    wedge reverse() const { return {i, v, u, w}; }
    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)};
}
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;
}
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});
    }
    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; })) {
        graph<0, wedge<ll>, 1> sp_dag(n);
        for(auto [i, u, v, w] : g.edges) {
            if(ds[u] + w + dt[v] == ds[n]) {
                sp_dag.add_edge({i, u, v, w});
            }
        }
        auto [cut_edge, _2eccs] = find_2eccs(sp_dag);
        bool increase = false;
        for(int i = 0; i < sp_dag.edges.size(); i++) {
            wedge<ll>& sp_edge = sp_dag.edges[i];
            increase |= cut_edge[i] and sp_edge.i != m - 1;
        }
        cout << ds[n] + increase << endl;
    } else if(m == n - 1) {
        auto path = construct_path(g, ps, n);
        set<pair<int, int>> in_path;
        for(int i = 0; i < path.size() - 1; i++) {
            in_path.insert({path[i], path[i + 1]});
        }
        ll max_replace = 0;
        ll ans = ds[n];
        for(int ii = g.edges.size() - 1; ii >= 0; ii--) {
            auto [i, u, v, w] = g.edges[ii];
            if(in_path.count({u, v})) {
                ans = max(ans, ds[u] + w + max_replace + dt[v]);
            }
            if(ii % 2 == 0) {
                max_replace = max(max_replace, w);
            }
        }
        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:121:26: 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 i = 0; i < sp_dag.edges.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~~~~~~~
Aesthetic.cpp:129:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for(int i = 0; i < path.size() - 1; i++) {
      |                        ~~^~~~~~~~~~~~~~~~~
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:119: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 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 360 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 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 360 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 352 ms 588 KB Output is correct
10 Correct 353 ms 596 KB Output is correct
11 Correct 258 ms 596 KB Output is correct
12 Correct 263 ms 596 KB Output is correct
13 Correct 151 ms 460 KB Output is correct
14 Correct 201 ms 528 KB Output is correct
15 Correct 151 ms 524 KB Output is correct
16 Correct 165 ms 520 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 39400 KB Output is correct
2 Correct 596 ms 45084 KB Output is correct
3 Correct 575 ms 44388 KB Output is correct
4 Correct 578 ms 44416 KB Output is correct
5 Correct 654 ms 44608 KB Output is correct
6 Correct 563 ms 45684 KB Output is correct
7 Correct 580 ms 45464 KB Output is correct
8 Correct 568 ms 45792 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 43616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 49896 KB Output is correct
2 Correct 196 ms 62080 KB Output is correct
3 Correct 318 ms 64588 KB Output is correct
4 Correct 355 ms 64528 KB Output is correct
5 Correct 322 ms 64516 KB Output is correct
6 Correct 342 ms 64912 KB Output is correct
7 Correct 318 ms 64500 KB Output is correct
8 Correct 337 ms 64772 KB Output is correct
9 Correct 315 ms 64524 KB Output is correct
10 Correct 349 ms 65312 KB Output is correct
11 Correct 317 ms 64688 KB Output is correct
12 Correct 419 ms 52300 KB Output is correct
13 Correct 305 ms 64716 KB Output is correct
14 Correct 150 ms 74056 KB Output is correct
15 Correct 165 ms 74072 KB Output is correct
16 Correct 414 ms 51644 KB Output is correct
17 Correct 423 ms 50404 KB Output is correct
18 Correct 407 ms 51212 KB Output is correct
19 Correct 221 ms 62280 KB Output is correct
20 Correct 196 ms 62484 KB Output is correct
21 Correct 196 ms 62280 KB Output is correct
22 Correct 200 ms 62324 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 49896 KB Output is correct
2 Correct 196 ms 62080 KB Output is correct
3 Correct 318 ms 64588 KB Output is correct
4 Correct 355 ms 64528 KB Output is correct
5 Correct 322 ms 64516 KB Output is correct
6 Correct 342 ms 64912 KB Output is correct
7 Correct 318 ms 64500 KB Output is correct
8 Correct 337 ms 64772 KB Output is correct
9 Correct 315 ms 64524 KB Output is correct
10 Correct 349 ms 65312 KB Output is correct
11 Correct 317 ms 64688 KB Output is correct
12 Correct 419 ms 52300 KB Output is correct
13 Correct 305 ms 64716 KB Output is correct
14 Correct 150 ms 74056 KB Output is correct
15 Correct 165 ms 74072 KB Output is correct
16 Correct 414 ms 51644 KB Output is correct
17 Correct 423 ms 50404 KB Output is correct
18 Correct 407 ms 51212 KB Output is correct
19 Correct 221 ms 62280 KB Output is correct
20 Correct 196 ms 62484 KB Output is correct
21 Correct 196 ms 62280 KB Output is correct
22 Correct 200 ms 62324 KB Output is correct
23 Execution timed out 2071 ms 42068 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 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 360 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 352 ms 588 KB Output is correct
10 Correct 353 ms 596 KB Output is correct
11 Correct 258 ms 596 KB Output is correct
12 Correct 263 ms 596 KB Output is correct
13 Correct 151 ms 460 KB Output is correct
14 Correct 201 ms 528 KB Output is correct
15 Correct 151 ms 524 KB Output is correct
16 Correct 165 ms 520 KB Output is correct
17 Correct 564 ms 39400 KB Output is correct
18 Correct 596 ms 45084 KB Output is correct
19 Correct 575 ms 44388 KB Output is correct
20 Correct 578 ms 44416 KB Output is correct
21 Correct 654 ms 44608 KB Output is correct
22 Correct 563 ms 45684 KB Output is correct
23 Correct 580 ms 45464 KB Output is correct
24 Correct 568 ms 45792 KB Output is correct
25 Execution timed out 2083 ms 43616 KB Time limit exceeded
26 Halted 0 ms 0 KB -