Submission #475795

#TimeUsernameProblemLanguageResultExecution timeMemory
475795maomao90Aesthetic (NOI20_aesthetic)C++17
35 / 100
1872 ms38612 KiB
#include <bits/stdc++.h> using namespace std; template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} #define REP(i, s, e) for (int i = s; i < e; i++) #define RREP(i, s, e) for (int i = s; i >= e; i--) typedef long long ll; typedef long double ld; #define MP make_pair #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; #define MT make_tuple typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; #ifdef DEBUG #define debug(args...) printf(args) #else #define debug(args...) #endif #define INF 1000000005 #define LINF 1000000000000000005 #define MOD 1000000007 #define MAXN 300005 struct edge { int v, w, p; }; int n, m; vector<edge> adj[MAXN]; int a[MAXN], b[MAXN], w[MAXN], p[MAXN]; priority_queue<pll, vector<pll>, greater<pll>> pq; ll d1[MAXN], dn[MAXN]; void dij(int s, ll* d) { REP (i, 1, n + 1) { d[i] = LINF; } d[s] = 0; pq.push(MP(0, s)); while (!pq.empty()) { auto [ud, u] = pq.top(); pq.pop(); if (ud != d[u]) continue; for (edge e : adj[u]) { if (mnto(d[e.v], ud + e.w)) { pq.push(MP(d[e.v], e.v)); } } } } ll x; bool res; int dep[MAXN], low[MAXN], ptr; void dfs(int u, int p) { dep[u] = low[u] = ptr++; for (edge e : adj[u]) { if (e.v == p) continue; ll od = min(d1[u] + dn[e.v], d1[e.v] + dn[u]) + e.w; if (od > x) continue; if (dep[e.v] == -1) { dfs(e.v, u); if (res) return; mnto(low[u], low[e.v]); if (low[e.v] > dep[u] && od + e.p > x && dep[n] != -1 && dep[n] >= low[e.v]) { res = 1; return; } } else { mnto(low[u], dep[e.v]); } } } bool isPos(ll x) { ptr = 0; ::x = x; res = 0; memset(dep, -1, sizeof dep); dfs(1, -1); return res; } int main() { scanf("%d%d", &n, &m); REP (i, 0, m) { scanf("%d%d%d", &a[i], &b[i], &w[i]); } int mx = 0; RREP (i, m - 1, 0) { p[i] = mx; mxto(mx, w[i]); } REP (i, 0, m) { adj[a[i]].pb({b[i], w[i], p[i]}); adj[b[i]].pb({a[i], w[i], p[i]}); } dij(1, d1); dij(n, dn); ll lo = d1[n], hi = INF + d1[n], mid; while (lo < hi) { mid = lo + hi + 1 >> 1; if (isPos(mid)) { lo = mid; } else { hi = mid - 1; } } printf("%lld\n", lo + 1); return 0; }

Compilation message (stderr)

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:114:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |   mid = lo + hi + 1 >> 1;
      |         ~~~~~~~~^~~
Aesthetic.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
Aesthetic.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |   scanf("%d%d%d", &a[i], &b[i], &w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...