oj.uz

Submission #256992

# Submission time Handle Problem Language Result Execution time Memory
256992 2020-08-03T13:42:57 Z Bruteforceman Aesthetic (NOI20_aesthetic) C++11
35 / 100
 2000 ms 73524 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
const int logn = 19;
const long long inf = 1e16;
int anc[logn + 1][maxn];
int l[maxn], r[maxn], w[maxn];
vector <int> g[maxn], t[maxn];
long long ans[maxn];
int dep[maxn];

int n, m;

struct data {
  long long dist;
  int node;
  data (long long dist, int node) : dist(dist), node(node) {}
  data () {}
  bool operator < (data d) const {
    return dist > d.dist;
  }
};

vector <long long> dijstra(int root) {
  priority_queue <data> Q;

  vector <long long> dist (n, inf);
  Q.emplace(0, root);
  dist[root] = 0;
  while(!Q.empty()) {
    int node = Q.top().node;
    long long var = Q.top().dist;
    Q.pop();
    if(var != dist[node]) continue;
    for(int e : g[node]) {
      int x = l[e] ^ r[e] ^ node;
      if(w[e] + dist[node] < dist[x]) {
        dist[x] = w[e] + dist[node];
        Q.emplace(dist[x], x);
      }
    }
  }
  return dist;
}
void dfs(int x) {
  for(int i = 1; i <= logn; i++) {
    anc[i][x] = anc[i - 1][anc[i - 1][x]];
  }
  for(int i : t[x]) {
    dep[i] = 1 + dep[x];
    anc[0][i] = x;
    dfs(i);
  }
}
int lca(int x, int y) {
  if(dep[x] > dep[y]) swap(x, y);
  for(int i = logn; i >= 0; i--) {
    if(dep[y] - (1 << i) >= dep[x]) {
      y = anc[i][y];
    }
  }
  if(x == y) return x;
  for(int i = logn; i >= 0; i--) {
    if(anc[i][x] != anc[i][y]) {
      x = anc[i][x];
      y = anc[i][y];
    }
  }
  return anc[0][x];
}
int main() {
  scanf("%d %d", &n, &m);
  for(int i = 0; i < m; i++) {
    scanf("%d %d %d", &l[i], &r[i], &w[i]);
    l[i] -= 1;
    r[i] -= 1;
    g[l[i]].push_back(i);
    g[r[i]].push_back(i);
  }
  vector <long long> forward = dijstra(0);
  vector <int> par (n);
  for(int i = 1; i < n; i++) {
    for(int e : g[i]) {
      int x = l[e] ^ r[e] ^ i;
      if(forward[x] + w[e] == forward[i]) {
        par[i] = e;
        t[x].push_back(i);
        break;
      }
    }
  }
  dfs(0);
  vector <long long> backward = dijstra(n - 1);
  int cur = n - 1;
  vector <bool> onPath (m);
  while(cur != 0) {
    onPath[par[cur]] = true;
    cur = anc[0][cur];
  }
  for(int i = 0; i < m; i++) ans[i] = inf;
  for(int i = 0; i < m; i++) {
    if(onPath[i]) continue;
    ans[i] = forward[n - 1];
    int p = lca(l[i], n - 1);
    int q = lca(r[i], n - 1);
    if(dep[p] > dep[q])  {
      swap(p, q);
      swap(l[i], r[i]);
    }
    while(p != q) {
      ans[par[q]] = min(ans[par[q]], w[i] + forward[l[i]] + backward[r[i]]);      q = anc[0][q];
    }
  }
  int mx = w[m - 1];
  long long res = 0;
  for(int i = m - 2; i >= 0; i--) {
    long long p = forward[l[i]] + mx + w[i] + backward[r[i]];
    long long q = forward[r[i]] + mx + w[i] + backward[l[i]];
    res = max(res, min({ans[i], p, q}));
    mx = max(mx, w[i]);
  }
  printf("%lld\n", res);
  return 0;
}

Compilation message

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:72: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:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &l[i], &r[i], &w[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14592 KB Output is correct
2 Correct 9 ms 14592 KB Output is correct
3 Correct 10 ms 14592 KB Output is correct
4 Correct 11 ms 14592 KB Output is correct
5 Correct 9 ms 14592 KB Output is correct
6 Correct 9 ms 14592 KB Output is correct
7 Correct 9 ms 14592 KB Output is correct
8 Correct 11 ms 14592 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14592 KB Output is correct
2 Correct 9 ms 14592 KB Output is correct
3 Correct 10 ms 14592 KB Output is correct
4 Correct 11 ms 14592 KB Output is correct
5 Correct 9 ms 14592 KB Output is correct
6 Correct 9 ms 14592 KB Output is correct
7 Correct 9 ms 14592 KB Output is correct
8 Correct 11 ms 14592 KB Output is correct
9 Correct 12 ms 14848 KB Output is correct
10 Correct 11 ms 14848 KB Output is correct
11 Correct 11 ms 14828 KB Output is correct
12 Correct 11 ms 14848 KB Output is correct
13 Correct 11 ms 14720 KB Output is correct
14 Correct 11 ms 14720 KB Output is correct
15 Correct 11 ms 14720 KB Output is correct
16 Correct 11 ms 14720 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1208 ms 72092 KB Output is correct
2 Correct 1136 ms 72716 KB Output is correct
3 Correct 1183 ms 71576 KB Output is correct
4 Correct 1136 ms 71672 KB Output is correct
5 Correct 1331 ms 71908 KB Output is correct
6 Correct 1327 ms 73260 KB Output is correct
7 Correct 1392 ms 73016 KB Output is correct
8 Correct 1397 ms 73448 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1499 ms 73292 KB Output is correct
2 Correct 1257 ms 72312 KB Output is correct
3 Correct 999 ms 72312 KB Output is correct
4 Correct 1049 ms 73524 KB Output is correct
5 Correct 1225 ms 72384 KB Output is correct
6 Correct 1077 ms 72440 KB Output is correct
7 Correct 1342 ms 72392 KB Output is correct
8 Correct 1351 ms 72568 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 988 ms 56544 KB Output is correct
2 Correct 344 ms 66052 KB Output is correct
3 Correct 487 ms 42136 KB Output is correct
4 Correct 547 ms 42312 KB Output is correct
5 Correct 501 ms 42308 KB Output is correct
6 Correct 562 ms 42204 KB Output is correct
7 Correct 509 ms 42324 KB Output is correct
8 Correct 465 ms 42292 KB Output is correct
9 Correct 547 ms 42308 KB Output is correct
10 Correct 469 ms 42436 KB Output is correct
11 Correct 471 ms 42388 KB Output is correct
12 Correct 985 ms 56100 KB Output is correct
13 Correct 509 ms 42360 KB Output is correct
14 Execution timed out 2087 ms 62328 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 988 ms 56544 KB Output is correct
2 Correct 344 ms 66052 KB Output is correct
3 Correct 487 ms 42136 KB Output is correct
4 Correct 547 ms 42312 KB Output is correct
5 Correct 501 ms 42308 KB Output is correct
6 Correct 562 ms 42204 KB Output is correct
7 Correct 509 ms 42324 KB Output is correct
8 Correct 465 ms 42292 KB Output is correct
9 Correct 547 ms 42308 KB Output is correct
10 Correct 469 ms 42436 KB Output is correct
11 Correct 471 ms 42388 KB Output is correct
12 Correct 985 ms 56100 KB Output is correct
13 Correct 509 ms 42360 KB Output is correct
14 Execution timed out 2087 ms 62328 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14592 KB Output is correct
2 Correct 9 ms 14592 KB Output is correct
3 Correct 10 ms 14592 KB Output is correct
4 Correct 11 ms 14592 KB Output is correct
5 Correct 9 ms 14592 KB Output is correct
6 Correct 9 ms 14592 KB Output is correct
7 Correct 9 ms 14592 KB Output is correct
8 Correct 11 ms 14592 KB Output is correct
9 Correct 12 ms 14848 KB Output is correct
10 Correct 11 ms 14848 KB Output is correct
11 Correct 11 ms 14828 KB Output is correct
12 Correct 11 ms 14848 KB Output is correct
13 Correct 11 ms 14720 KB Output is correct
14 Correct 11 ms 14720 KB Output is correct
15 Correct 11 ms 14720 KB Output is correct
16 Correct 11 ms 14720 KB Output is correct
17 Correct 1208 ms 72092 KB Output is correct
18 Correct 1136 ms 72716 KB Output is correct
19 Correct 1183 ms 71576 KB Output is correct
20 Correct 1136 ms 71672 KB Output is correct
21 Correct 1331 ms 71908 KB Output is correct
22 Correct 1327 ms 73260 KB Output is correct
23 Correct 1392 ms 73016 KB Output is correct
24 Correct 1397 ms 73448 KB Output is correct
25 Correct 1499 ms 73292 KB Output is correct
26 Correct 1257 ms 72312 KB Output is correct
27 Correct 999 ms 72312 KB Output is correct
28 Correct 1049 ms 73524 KB Output is correct
29 Correct 1225 ms 72384 KB Output is correct
30 Correct 1077 ms 72440 KB Output is correct
31 Correct 1342 ms 72392 KB Output is correct
32 Correct 1351 ms 72568 KB Output is correct
33 Correct 988 ms 56544 KB Output is correct
34 Correct 344 ms 66052 KB Output is correct
35 Correct 487 ms 42136 KB Output is correct
36 Correct 547 ms 42312 KB Output is correct
37 Correct 501 ms 42308 KB Output is correct
38 Correct 562 ms 42204 KB Output is correct
39 Correct 509 ms 42324 KB Output is correct
40 Correct 465 ms 42292 KB Output is correct
41 Correct 547 ms 42308 KB Output is correct
42 Correct 469 ms 42436 KB Output is correct
43 Correct 471 ms 42388 KB Output is correct
44 Correct 985 ms 56100 KB Output is correct
45 Correct 509 ms 42360 KB Output is correct
46 Execution timed out 2087 ms 62328 KB Time limit exceeded
47 Halted 0 ms 0 KB -