Submission #261379

#TimeUsernameProblemLanguageResultExecution timeMemory
261379NightlightAesthetic (NOI20_aesthetic)C++14
Compilation error
0 ms0 KiB
#include <cstdio> #include <queue> #include <cstring> #define pii pair<long long, int> using namespace std; int N, M; vector<pii> adj[300005]; priority_queue<pii, vector<pii>, greater<pii>> pq; long long dist[2][300005]; int U[300005], V[300005]; bool can[300005], ada[300005]; long long W[300005], best[300005]; vector<pair<int, int>> adj2[300005]; int disc[300005], low[300005], waktu, need; long long p1[300005], p2[300005], pp1[300005], pp2[300005]; bool ok; void BFS(int id, int st) { memset(ada, 0, sizeof(ada)); pq.emplace(0LL, st); dist[id][st] = 0; int u, v; long long len, w; while(!pq.empty()) { u = pq.top().second; len = pq.top().first; pq.pop(); if(len != dist[u]) continue; for(pii now : adj[u]) { v = now.second; w = now.first; if(dist[id][v] > len + w) { dist[id][v] = len + w; pq.emplace(dist[id][v], v); } } } } void DFS(int u, int p) { disc[u] = low[u] = ++waktu; int v, id; for(pair<int, int> now : adj2[u]) { id = now.second; if(ada[id] == 0) continue; v = now.first; if(disc[v] <= need) { DFS(v, u); if(can[id] && low[v] > disc[u] && disc[N] >= disc[v] && disc[N] <= waktu) { ok = 1; }else low[u] = min(low[u], low[v]); }else if(p != v) { low[u] = min(low[u], disc[v]); } } } bool check(long long now) { ok = 0; need = waktu; for(int i = 1; i <= M; i++) { if(p1[i] > now && p2[i] > now) ada[i] = 0; else ada[i] = 1; if(pp1[i] > now && pp2[i] > now) can[i] = 1; else can[i] = 0; } DFS(1, 0); if(disc[N] <= need) return 1; if(ok) return 1; return 0; } int main() { memset(dist, 0x3f3f3f3f, sizeof(dist)); scanf("%d %d", &N, &M); int u, v; long long w; for(int i = 1; i <= M; i++) { scanf("%d %d %lld", &u, &v, &w); U[i] = u, V[i] = v, W[i] = w; adj[u].emplace_back(w, v); adj[v].emplace_back(w, u); adj2[u].emplace_back(v, i); adj2[v].emplace_back(u, i); } for(int i = M - 1; i > 0; i--) { best[i] = max(best[i + 1], W[i + 1]); } BFS(0, 1); BFS(1, N); for(int i = 1; i <= M; i++) { p1[i] = dist[0][U[i]] + W[i] + dist[1][V[i]]; p2[i] = dist[0][V[i]] + W[i] + dist[1][U[i]]; pp1[i] = dist[0][U[i]] + best[i] + W[i] + dist[1][V[i]]; pp2[i] = dist[0][V[i]] + best[i] + W[i] + dist[1][U[i]]; } long long l = dist[0][N], r = dist[0][N] + 1000000000, res = dist[0][N], mid; while(l <= r) { mid = (l + r) >> 1; if(check(mid)) { l = mid + 1; res = l; }else r = mid - 1; } printf("%lld\n", res); }

Compilation message (stderr)

Aesthetic.cpp: In function 'void BFS(int, int)':
Aesthetic.cpp:29:21: error: ISO C++ forbids comparison between pointer and integer [-fpermissive]
     if(len != dist[u]) continue;
                     ^
Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &M);
   ~~~~~^~~~~~~~~~~~~~~~~
Aesthetic.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld", &u, &v, &w);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~