Submission #261315

#	Time	Username	Problem	Language	Result	Execution time	Memory
261315		Nightlight	Aesthetic (NOI20_aesthetic)	C++14	100 / 100	1211 ms	74200 KiB

Aesthetic

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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;
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;
//    printf("%lld\n", len);
    pq.pop();
    if(ada[u]) continue;
    ada[u] = 1;
    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;
//  cout << "\n";
  for(int i = 1; i <= M; i++) {
    if(dist[0][U[i]] + W[i] + dist[1][V[i]] > now && dist[0][V[i]] + W[i] + dist[1][U[i]] > now) ada[i] = 0;
    else ada[i] = 1;
    if(dist[0][U[i]] + best[i] + W[i] + dist[1][V[i]] > now && dist[0][V[i]] + best[i] + W[i] + dist[1][U[i]] > now) can[i] = 1;
    else can[i] = 0;
  }
  DFS(1, 0);
//  cout << now << " " << disc[N] << " " << ok << "\n";
  if(disc[N] <= need) return 1;
  if(ok) return 1;
  return 0;
}

int main() {
//  ios_base::sync_with_stdio(0);
  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);
//  if(N + M > 4000 && M > N + 1) return -1;
  long long l = dist[0][N], r = dist[0][N] + best[1], 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);
//  scanf("%d\n", &N);
//  cin >> N;
}

Compilation message (stderr)

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:82: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:86: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);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22
• Subtask 7: 27 / 27