Submission #603406

#TimeUsernameProblemLanguageResultExecution timeMemory
603406verngutzAesthetic (NOI20_aesthetic)C++17
16 / 100
1971 ms177408 KiB
#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)}; } 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(auto [i, u, v, w, dw] : g.edges) { if(ds[u] + w + dt[v] < ds[n] + delta) { sp_dag.add_edge({i, u, v, w, dw}); } } 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 ds[u] + w + dw + dt[v] >= ds[n] + delta; } if(increase) { ans = ds[n] + delta; } } cout << ans << endl; return 0; }

Compilation message (stderr)

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:119: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]
  119 |         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:117: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]) {
      |                        ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...