Submission #367653

#TimeUsernameProblemLanguageResultExecution timeMemory
367653534351Aesthetic (NOI20_aesthetic)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; template<class T, class U> void ckmin(T &a, U b) { if (a > b) a = b; } template<class T, class U> void ckmax(T &a, U b) { if (a < b) a = b; } #define MP make_pair #define PB push_back #define LB lower_bound #define UB upper_bound #define fi first #define se second #define SZ(x) ((int) (x).size()) #define ALL(x) (x).begin(), (x).end() #define FOR(i, a, b) for (auto i = (a); i < (b); i++) #define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--) const int MAXN = 3e5 + 13; const long long LLINF = 3e18; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; typedef vector<pii> vpi; typedef vector<pll> vpl; typedef pair<pll, int> ppi; int N, M, C, T; vector<ppi> edge[MAXN]; ll dist[2][MAXN]; ll D; int st[MAXN], ft[MAXN]; bitset<MAXN> seen; vi bcc[MAXN]; vpi edges; void dijkstra(int u) { bool b = (u > 0); fill(dist[b], dist[b] + N + 1, LLINF); dist[b][u] = 0; priority_queue<pll, vector<pll>, greater<pll> > pq; pq.push({0, u}); while(!pq.empty()) { ll d = pq.top().fi; int u = pq.top().se; pq.pop(); if (d != dist[u]) continue; for (auto e : edge[u]) { int v = e.se; ll nd = d + e.fi.fi; if (nd < dist[b][v]) { dist[b][v] = nd; pq.push({nd, v}); } } } } void dfs(int u, int p) { st[u] = T; ft[u] = T; T++; seen[u] = true; for (auto e : edge[u]) { int v = e.se; ll d = e.fi.fi; //if this is not on any shortest paths we just ignore it. if (dist[0][u] + d + dist[1][v] >= D && dist[1][u] + d + dist[0][v] >= D) continue; //oh no it is part of a path shorter than D so we legit care about it. if (v == p) continue; if (seen[v]) { if (st[v] > st[u]) continue; edges.PB({u, v}); ckmin(ft[u], st[v]); continue; } edges.PB({u, v}); dfs(v, u); ckmin(ft[u], ft[v]); if (ft[v] >= st[u]) { while(!edges.empty()) { pii p = edges.back(); edges.pop_back(); bcc[C].PB(p.fi); bcc[C].PB(p.se); if (p == MP(u, v)) break; } C++; } } } bool check() { //can you make the dist >D? //ans is YES if there's a bridge & this thing extends dist by more than D. T = 0; fill(st, st + N, 0); fill(ft, ft + N, 0); seen.reset(); FOR(i, 0, C) bcc[i].clear(); C = 0; FOR(i, 0, N) { if (seen[i]) continue; dfs(i, N); } set<pii> bridges; FOR(i, 0, C) { sort(ALL(bcc[i])); bcc[i].erase(unique(ALL(bcc[i])), bcc[i].end()); if (SZ(bcc[i]) == 2) { bridges.insert({bcc[i][0], bcc[i][1]}); } } FOR(u, 0, N) { for (auto e : edge[u]) { int v = e.se; ll mx = e.fi.se; if (bridges.find({u, v}) == bridges.end()) continue; if (dist[0][u] + mx + dist[1][v] >= D && dist[1][u] + mx + dist[0][v] >= D) return true; } } return false; //now just check if there's something we can extend that is a bridge. } int32_t main() { cout << fixed << setprecision(12); cerr << fixed << setprecision(4); ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> M; vector<array<int, 3> > eds(M); FOR(i, 0, M) { int a, b, w; cin >> a >> b >> w; a--; b--; if (a == b) continue; eds.PB({a, b, w}); } reverse(ALL(eds)); int mx = 0; for (auto e : eds) { int a = e[0], b = e[1], w = e[2]; edge[a].PB({{w, w + mx}, b}); edge[b].PB({{w, w + mx}, a}); ckmax(mx, w); } dijkstra(0); dijkstra(N - 1); ll lo = dist[0][N - 1], hi = 2 * lo + 1; while(hi > lo) { D = (hi + lo + 1) >> 1; if (check()) lo = D; else hi = D - 1; } cout << lo << '\n'; return 0; }

Compilation message (stderr)

Aesthetic.cpp: In function 'void dijkstra(int)':
Aesthetic.cpp:60:24: error: ISO C++ forbids comparison between pointer and integer [-fpermissive]
   60 |         if (d != dist[u]) continue;
      |                        ^