oj.uz

Submission #261371

# Submission time Handle Problem Language Result Execution time Memory
261371 2020-08-11T16:46:13 Z Nightlight Aesthetic (NOI20_aesthetic) C++14
35 / 100
 2000 ms 65284 KB 
#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;
    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;
  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);
  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);
  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

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);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19456 KB Output is correct
2 Correct 14 ms 19456 KB Output is correct
3 Correct 16 ms 19456 KB Output is correct
4 Correct 15 ms 19456 KB Output is correct
5 Correct 15 ms 19456 KB Output is correct
6 Correct 15 ms 19456 KB Output is correct
7 Correct 14 ms 19584 KB Output is correct
8 Correct 15 ms 19456 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19456 KB Output is correct
2 Correct 14 ms 19456 KB Output is correct
3 Correct 16 ms 19456 KB Output is correct
4 Correct 15 ms 19456 KB Output is correct
5 Correct 15 ms 19456 KB Output is correct
6 Correct 15 ms 19456 KB Output is correct
7 Correct 14 ms 19584 KB Output is correct
8 Correct 15 ms 19456 KB Output is correct
9 Correct 20 ms 19712 KB Output is correct
10 Correct 20 ms 19712 KB Output is correct
11 Correct 17 ms 19712 KB Output is correct
12 Correct 15 ms 19704 KB Output is correct
13 Correct 17 ms 19712 KB Output is correct
14 Correct 17 ms 19712 KB Output is correct
15 Correct 16 ms 19712 KB Output is correct
16 Correct 16 ms 19712 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1067 ms 58104 KB Output is correct
2 Correct 1096 ms 57804 KB Output is correct
3 Correct 1006 ms 57868 KB Output is correct
4 Correct 1064 ms 57804 KB Output is correct
5 Correct 1064 ms 57996 KB Output is correct
6 Correct 1022 ms 58744 KB Output is correct
7 Correct 973 ms 58556 KB Output is correct
8 Correct 1018 ms 58872 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1044 ms 58744 KB Output is correct
2 Correct 1115 ms 58268 KB Output is correct
3 Correct 1055 ms 57432 KB Output is correct
4 Correct 1051 ms 57448 KB Output is correct
5 Correct 1102 ms 58064 KB Output is correct
6 Correct 1044 ms 58232 KB Output is correct
7 Correct 1055 ms 58332 KB Output is correct
8 Correct 1047 ms 58604 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 65284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 65284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19456 KB Output is correct
2 Correct 14 ms 19456 KB Output is correct
3 Correct 16 ms 19456 KB Output is correct
4 Correct 15 ms 19456 KB Output is correct
5 Correct 15 ms 19456 KB Output is correct
6 Correct 15 ms 19456 KB Output is correct
7 Correct 14 ms 19584 KB Output is correct
8 Correct 15 ms 19456 KB Output is correct
9 Correct 20 ms 19712 KB Output is correct
10 Correct 20 ms 19712 KB Output is correct
11 Correct 17 ms 19712 KB Output is correct
12 Correct 15 ms 19704 KB Output is correct
13 Correct 17 ms 19712 KB Output is correct
14 Correct 17 ms 19712 KB Output is correct
15 Correct 16 ms 19712 KB Output is correct
16 Correct 16 ms 19712 KB Output is correct
17 Correct 1067 ms 58104 KB Output is correct
18 Correct 1096 ms 57804 KB Output is correct
19 Correct 1006 ms 57868 KB Output is correct
20 Correct 1064 ms 57804 KB Output is correct
21 Correct 1064 ms 57996 KB Output is correct
22 Correct 1022 ms 58744 KB Output is correct
23 Correct 973 ms 58556 KB Output is correct
24 Correct 1018 ms 58872 KB Output is correct
25 Correct 1044 ms 58744 KB Output is correct
26 Correct 1115 ms 58268 KB Output is correct
27 Correct 1055 ms 57432 KB Output is correct
28 Correct 1051 ms 57448 KB Output is correct
29 Correct 1102 ms 58064 KB Output is correct
30 Correct 1044 ms 58232 KB Output is correct
31 Correct 1055 ms 58332 KB Output is correct
32 Correct 1047 ms 58604 KB Output is correct
33 Execution timed out 2057 ms 65284 KB Time limit exceeded
34 Halted 0 ms 0 KB -