Submission #261357

#TimeUsernameProblemLanguageResultExecution timeMemory
261357BertedAesthetic (NOI20_aesthetic)C++14
35 / 100
2041 ms49188 KiB
#include <iostream> #include <vector> #include <queue> #include <tuple> #include <bitset> #define ll long long #define vi vector<int> #define pii pair<ll, int> #define fst first #define snd second #define pub push_back #define vpi vector<pii> using namespace std; namespace fastIO { char outString[64]; inline int getchar_unlocked() {return getchar();} inline void putchar_unlocked(int x) {putchar(x);} inline int charInput() {return getchar_unlocked();} inline void charOutput(int x) {putchar_unlocked(x);} inline bool isNum(int c) {return '0' <= c && c <= '9';} inline int intInput() { int c = 0, ret = 0; bool neg = 0; while (!isNum(c)) { c = getchar_unlocked(); if (c == '-') {neg = 1;} } while (isNum(c)) {ret = ret * 10 + c - '0'; c = getchar_unlocked();} return (neg) ? -ret : ret; } inline void intOutput(ll x) { int ss = 0; while (x) {outString[ss++] = x % 10 + '0'; x /= 10;} if (!ss) outString[ss++] = '0'; for (int i = ss - 1; i >= 0; i--) putchar_unlocked(outString[i]); } inline void strOutput(string s) { for (auto &c : s) putchar_unlocked(c); } } const ll INF = 1e17; int n, m, pref[300069], cst[300069], idx = 0, vis[300069], low[300069], pid = 0; vpi adj[300069]; pii edge[300069]; ll dst[2][300069], de[2][300069], lim; priority_queue<pii, vector<pii>, greater<pii>> pq; bool bt[300069]; bool ans = 0; inline void runDijkstra(int s, int id) { for (int i = 0; i < n; i++) {dst[id][i] = INF; bt[i] = 0;} dst[id][s] = 0; pq.emplace(0, s); while (pq.size()) { int u = pq.top().snd; pq.pop(); if (!bt[u]) { bt[u] = 1; for (auto v : adj[u]) { if (dst[id][u] + cst[v.fst] < dst[id][v.snd]) { dst[id][v.snd] = dst[id][u] + cst[v.fst]; pq.emplace(dst[id][v.snd], v.snd); } } } } } void bCheck(int u, int p) { vis[u] = low[u] = idx++; //cout << "Visit : " << idx << "\n"; for (auto v : adj[u]) { if (v.snd != p && de[0][v.fst] <= lim) { if (vis[v.snd] < pid) { bCheck(v.snd, u); if (ans) return; low[u] = min(low[v.snd], low[u]); if (low[v.snd] > vis[u] && (vis[n - 1] >= pid && low[v.snd] <= vis[n - 1]) && de[1][v.fst] > lim) {ans = 1; return;} } else low[u] = min(vis[v.snd], low[u]); } } } int32_t main() { // ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("5-1.in", "r", stdin); n = fastIO :: intInput(); m = fastIO :: intInput(); for (int i = 0; i < n; i++) vis[i] = -1; for (int i = 0; i < m; i++) { int u, v, w; u = fastIO :: intInput(); v = fastIO :: intInput(); w = fastIO :: intInput(); u--; v--; adj[u].emplace_back(i, v); adj[v].emplace_back(i, u); cst[i] = pref[i] = w; edge[i] = {u, v}; } for (int i = m - 2; i >= 0; i--) {pref[i] = max(pref[i], pref[i + 1]);} runDijkstra(0, 0); runDijkstra(n - 1, 1); for (int i = 0; i < m; i++) { de[0][i] = min(dst[0][edge[i].fst] + dst[1][edge[i].snd], dst[1][edge[i].fst] + dst[0][edge[i].snd]) + cst[i]; de[1][i] = de[0][i] + pref[i + 1]; } // cout << "Dijkstra done\n"; ll L = dst[0][n - 1], R = dst[0][n - 1] + 1000000000; while (L < R) { ll M = L + R >> 1; lim = M; ans = 0; pid = idx; bCheck(0, -1); if (ans) L = M + 1; else R = M; } fastIO :: intOutput(L); fastIO :: charOutput('\n'); return 0; }

Compilation message (stderr)

Aesthetic.cpp: In function 'int32_t main()':
Aesthetic.cpp:134:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll M = L + R >> 1; lim = M; ans = 0; pid = idx;
          ~~^~~
#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...