oj.uz

Submission #261315

# Submission time Handle Problem Language Result Execution time Memory
261315 2020-08-11T16:10:34 Z Nightlight Aesthetic (NOI20_aesthetic) C++14
100 / 100
 1211 ms 74200 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19456 KB Output is correct
2 Correct 15 ms 19456 KB Output is correct
3 Correct 15 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 16 ms 19432 KB Output is correct
7 Correct 14 ms 19456 KB Output is correct
8 Correct 16 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 15 ms 19456 KB Output is correct
3 Correct 15 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 16 ms 19432 KB Output is correct
7 Correct 14 ms 19456 KB Output is correct
8 Correct 16 ms 19456 KB Output is correct
9 Correct 16 ms 19712 KB Output is correct
10 Correct 19 ms 19712 KB Output is correct
11 Correct 17 ms 19712 KB Output is correct
12 Correct 17 ms 19712 KB Output is correct
13 Correct 17 ms 19712 KB Output is correct
14 Correct 17 ms 19712 KB Output is correct
15 Correct 17 ms 19712 KB Output is correct
16 Correct 18 ms 19840 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1083 ms 56312 KB Output is correct
2 Correct 1026 ms 56184 KB Output is correct
3 Correct 1073 ms 55952 KB Output is correct
4 Correct 1153 ms 55952 KB Output is correct
5 Correct 1179 ms 56184 KB Output is correct
6 Correct 1144 ms 56848 KB Output is correct
7 Correct 1108 ms 56808 KB Output is correct
8 Correct 1148 ms 57116 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1160 ms 56952 KB Output is correct
2 Correct 969 ms 56312 KB Output is correct
3 Correct 1065 ms 55556 KB Output is correct
4 Correct 972 ms 55544 KB Output is correct
5 Correct 1211 ms 56316 KB Output is correct
6 Correct 1056 ms 56056 KB Output is correct
7 Correct 1063 ms 56468 KB Output is correct
8 Correct 963 ms 56568 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 53972 KB Output is correct
2 Correct 289 ms 56056 KB Output is correct
3 Correct 475 ms 62072 KB Output is correct
4 Correct 472 ms 61996 KB Output is correct
5 Correct 470 ms 61944 KB Output is correct
6 Correct 505 ms 62072 KB Output is correct
7 Correct 510 ms 61944 KB Output is correct
8 Correct 492 ms 62200 KB Output is correct
9 Correct 507 ms 62320 KB Output is correct
10 Correct 543 ms 62460 KB Output is correct
11 Correct 535 ms 62072 KB Output is correct
12 Correct 729 ms 58348 KB Output is correct
13 Correct 492 ms 62148 KB Output is correct
14 Correct 252 ms 73336 KB Output is correct
15 Correct 247 ms 73464 KB Output is correct
16 Correct 627 ms 58860 KB Output is correct
17 Correct 678 ms 57984 KB Output is correct
18 Correct 743 ms 58084 KB Output is correct
19 Correct 309 ms 56060 KB Output is correct
20 Correct 314 ms 56440 KB Output is correct
21 Correct 306 ms 56056 KB Output is correct
22 Correct 321 ms 56184 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 53972 KB Output is correct
2 Correct 289 ms 56056 KB Output is correct
3 Correct 475 ms 62072 KB Output is correct
4 Correct 472 ms 61996 KB Output is correct
5 Correct 470 ms 61944 KB Output is correct
6 Correct 505 ms 62072 KB Output is correct
7 Correct 510 ms 61944 KB Output is correct
8 Correct 492 ms 62200 KB Output is correct
9 Correct 507 ms 62320 KB Output is correct
10 Correct 543 ms 62460 KB Output is correct
11 Correct 535 ms 62072 KB Output is correct
12 Correct 729 ms 58348 KB Output is correct
13 Correct 492 ms 62148 KB Output is correct
14 Correct 252 ms 73336 KB Output is correct
15 Correct 247 ms 73464 KB Output is correct
16 Correct 627 ms 58860 KB Output is correct
17 Correct 678 ms 57984 KB Output is correct
18 Correct 743 ms 58084 KB Output is correct
19 Correct 309 ms 56060 KB Output is correct
20 Correct 314 ms 56440 KB Output is correct
21 Correct 306 ms 56056 KB Output is correct
22 Correct 321 ms 56184 KB Output is correct
23 Correct 787 ms 59780 KB Output is correct
24 Correct 387 ms 56184 KB Output is correct
25 Correct 476 ms 58104 KB Output is correct
26 Correct 470 ms 57324 KB Output is correct
27 Correct 469 ms 57416 KB Output is correct
28 Correct 506 ms 58488 KB Output is correct
29 Correct 478 ms 57720 KB Output is correct
30 Correct 508 ms 57848 KB Output is correct
31 Correct 504 ms 58220 KB Output is correct
32 Correct 477 ms 57592 KB Output is correct
33 Correct 482 ms 58360 KB Output is correct
34 Correct 764 ms 59128 KB Output is correct
35 Correct 498 ms 58104 KB Output is correct
36 Correct 242 ms 72788 KB Output is correct
37 Correct 244 ms 73560 KB Output is correct
38 Correct 776 ms 58988 KB Output is correct
39 Correct 790 ms 58476 KB Output is correct
40 Correct 792 ms 59792 KB Output is correct
41 Correct 401 ms 56256 KB Output is correct
42 Correct 409 ms 56184 KB Output is correct
43 Correct 358 ms 56312 KB Output is correct
44 Correct 341 ms 56188 KB Output is correct

Subtask #7
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19456 KB Output is correct
2 Correct 15 ms 19456 KB Output is correct
3 Correct 15 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 16 ms 19432 KB Output is correct
7 Correct 14 ms 19456 KB Output is correct
8 Correct 16 ms 19456 KB Output is correct
9 Correct 16 ms 19712 KB Output is correct
10 Correct 19 ms 19712 KB Output is correct
11 Correct 17 ms 19712 KB Output is correct
12 Correct 17 ms 19712 KB Output is correct
13 Correct 17 ms 19712 KB Output is correct
14 Correct 17 ms 19712 KB Output is correct
15 Correct 17 ms 19712 KB Output is correct
16 Correct 18 ms 19840 KB Output is correct
17 Correct 1083 ms 56312 KB Output is correct
18 Correct 1026 ms 56184 KB Output is correct
19 Correct 1073 ms 55952 KB Output is correct
20 Correct 1153 ms 55952 KB Output is correct
21 Correct 1179 ms 56184 KB Output is correct
22 Correct 1144 ms 56848 KB Output is correct
23 Correct 1108 ms 56808 KB Output is correct
24 Correct 1148 ms 57116 KB Output is correct
25 Correct 1160 ms 56952 KB Output is correct
26 Correct 969 ms 56312 KB Output is correct
27 Correct 1065 ms 55556 KB Output is correct
28 Correct 972 ms 55544 KB Output is correct
29 Correct 1211 ms 56316 KB Output is correct
30 Correct 1056 ms 56056 KB Output is correct
31 Correct 1063 ms 56468 KB Output is correct
32 Correct 963 ms 56568 KB Output is correct
33 Correct 618 ms 53972 KB Output is correct
34 Correct 289 ms 56056 KB Output is correct
35 Correct 475 ms 62072 KB Output is correct
36 Correct 472 ms 61996 KB Output is correct
37 Correct 470 ms 61944 KB Output is correct
38 Correct 505 ms 62072 KB Output is correct
39 Correct 510 ms 61944 KB Output is correct
40 Correct 492 ms 62200 KB Output is correct
41 Correct 507 ms 62320 KB Output is correct
42 Correct 543 ms 62460 KB Output is correct
43 Correct 535 ms 62072 KB Output is correct
44 Correct 729 ms 58348 KB Output is correct
45 Correct 492 ms 62148 KB Output is correct
46 Correct 252 ms 73336 KB Output is correct
47 Correct 247 ms 73464 KB Output is correct
48 Correct 627 ms 58860 KB Output is correct
49 Correct 678 ms 57984 KB Output is correct
50 Correct 743 ms 58084 KB Output is correct
51 Correct 309 ms 56060 KB Output is correct
52 Correct 314 ms 56440 KB Output is correct
53 Correct 306 ms 56056 KB Output is correct
54 Correct 321 ms 56184 KB Output is correct
55 Correct 787 ms 59780 KB Output is correct
56 Correct 387 ms 56184 KB Output is correct
57 Correct 476 ms 58104 KB Output is correct
58 Correct 470 ms 57324 KB Output is correct
59 Correct 469 ms 57416 KB Output is correct
60 Correct 506 ms 58488 KB Output is correct
61 Correct 478 ms 57720 KB Output is correct
62 Correct 508 ms 57848 KB Output is correct
63 Correct 504 ms 58220 KB Output is correct
64 Correct 477 ms 57592 KB Output is correct
65 Correct 482 ms 58360 KB Output is correct
66 Correct 764 ms 59128 KB Output is correct
67 Correct 498 ms 58104 KB Output is correct
68 Correct 242 ms 72788 KB Output is correct
69 Correct 244 ms 73560 KB Output is correct
70 Correct 776 ms 58988 KB Output is correct
71 Correct 790 ms 58476 KB Output is correct
72 Correct 792 ms 59792 KB Output is correct
73 Correct 401 ms 56256 KB Output is correct
74 Correct 409 ms 56184 KB Output is correct
75 Correct 358 ms 56312 KB Output is correct
76 Correct 341 ms 56188 KB Output is correct
77 Correct 952 ms 62436 KB Output is correct
78 Correct 594 ms 58488 KB Output is correct
79 Correct 659 ms 64608 KB Output is correct
80 Correct 667 ms 64424 KB Output is correct
81 Correct 634 ms 64356 KB Output is correct
82 Correct 639 ms 64248 KB Output is correct
83 Correct 691 ms 64696 KB Output is correct
84 Correct 577 ms 64808 KB Output is correct
85 Correct 575 ms 64248 KB Output is correct
86 Correct 575 ms 64376 KB Output is correct
87 Correct 741 ms 64636 KB Output is correct
88 Correct 954 ms 61296 KB Output is correct
89 Correct 724 ms 64612 KB Output is correct
90 Correct 405 ms 73384 KB Output is correct
91 Correct 407 ms 74200 KB Output is correct
92 Correct 928 ms 61808 KB Output is correct
93 Correct 924 ms 61296 KB Output is correct
94 Correct 826 ms 60784 KB Output is correct
95 Correct 664 ms 58640 KB Output is correct
96 Correct 687 ms 58488 KB Output is correct
97 Correct 708 ms 58676 KB Output is correct
98 Correct 752 ms 58488 KB Output is correct