oj.uz

Submission #261380

# Submission time Handle Problem Language Result Execution time Memory
261380 2020-08-11T16:54:18 Z Nightlight Aesthetic (NOI20_aesthetic) C++14
35 / 100
 2000 ms 75192 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;
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[id][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

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 15 ms 19456 KB Output is correct
2 Correct 14 ms 19456 KB Output is correct
3 Correct 15 ms 19456 KB Output is correct
4 Correct 14 ms 19456 KB Output is correct
5 Correct 16 ms 19456 KB Output is correct
6 Correct 17 ms 19456 KB Output is correct
7 Correct 19 ms 19456 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 15 ms 19456 KB Output is correct
2 Correct 14 ms 19456 KB Output is correct
3 Correct 15 ms 19456 KB Output is correct
4 Correct 14 ms 19456 KB Output is correct
5 Correct 16 ms 19456 KB Output is correct
6 Correct 17 ms 19456 KB Output is correct
7 Correct 19 ms 19456 KB Output is correct
8 Correct 15 ms 19456 KB Output is correct
9 Correct 15 ms 19840 KB Output is correct
10 Correct 16 ms 19840 KB Output is correct
11 Correct 16 ms 19712 KB Output is correct
12 Correct 16 ms 19840 KB Output is correct
13 Correct 15 ms 19840 KB Output is correct
14 Correct 15 ms 19840 KB Output is correct
15 Correct 19 ms 19840 KB Output is correct
16 Correct 23 ms 19840 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 947 ms 67960 KB Output is correct
2 Correct 905 ms 68088 KB Output is correct
3 Correct 869 ms 67696 KB Output is correct
4 Correct 901 ms 67756 KB Output is correct
5 Correct 949 ms 67956 KB Output is correct
6 Correct 1016 ms 68984 KB Output is correct
7 Correct 1008 ms 68728 KB Output is correct
8 Correct 957 ms 69172 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 68900 KB Output is correct
2 Correct 953 ms 68296 KB Output is correct
3 Correct 1037 ms 67704 KB Output is correct
4 Correct 910 ms 67576 KB Output is correct
5 Correct 918 ms 68088 KB Output is correct
6 Correct 925 ms 67960 KB Output is correct
7 Correct 982 ms 68088 KB Output is correct
8 Correct 907 ms 68500 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2086 ms 75192 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 2086 ms 75192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19456 KB Output is correct
2 Correct 14 ms 19456 KB Output is correct
3 Correct 15 ms 19456 KB Output is correct
4 Correct 14 ms 19456 KB Output is correct
5 Correct 16 ms 19456 KB Output is correct
6 Correct 17 ms 19456 KB Output is correct
7 Correct 19 ms 19456 KB Output is correct
8 Correct 15 ms 19456 KB Output is correct
9 Correct 15 ms 19840 KB Output is correct
10 Correct 16 ms 19840 KB Output is correct
11 Correct 16 ms 19712 KB Output is correct
12 Correct 16 ms 19840 KB Output is correct
13 Correct 15 ms 19840 KB Output is correct
14 Correct 15 ms 19840 KB Output is correct
15 Correct 19 ms 19840 KB Output is correct
16 Correct 23 ms 19840 KB Output is correct
17 Correct 947 ms 67960 KB Output is correct
18 Correct 905 ms 68088 KB Output is correct
19 Correct 869 ms 67696 KB Output is correct
20 Correct 901 ms 67756 KB Output is correct
21 Correct 949 ms 67956 KB Output is correct
22 Correct 1016 ms 68984 KB Output is correct
23 Correct 1008 ms 68728 KB Output is correct
24 Correct 957 ms 69172 KB Output is correct
25 Correct 1008 ms 68900 KB Output is correct
26 Correct 953 ms 68296 KB Output is correct
27 Correct 1037 ms 67704 KB Output is correct
28 Correct 910 ms 67576 KB Output is correct
29 Correct 918 ms 68088 KB Output is correct
30 Correct 925 ms 67960 KB Output is correct
31 Correct 982 ms 68088 KB Output is correct
32 Correct 907 ms 68500 KB Output is correct
33 Execution timed out 2086 ms 75192 KB Time limit exceeded
34 Halted 0 ms 0 KB -