oj.uz

답안 #1082981

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1082981 2024-09-02T09:29:24 Z avighna Aesthetic (NOI20_aesthetic) C++17
35 / 100
 2000 ms 86084 KB 
#include <bits/stdc++.h>

typedef long long ll;

struct To {
  ll v, w;
  ll i;
};

struct Edge {
  ll u, v, w;
};

const ll inf = 1e15;

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, m;
  std::cin >> n >> m;
  std::vector<std::vector<To>> adj(n + 1);
  std::vector<Edge> edges;
  for (ll i = 0, u, v, w; i < m; ++i) {
    std::cin >> u >> v >> w;
    adj[u].push_back({v, w, i});
    adj[v].push_back({u, w, i});
    edges.push_back({u, v, w});
  }

  auto sssp = [&](ll node) {
    std::vector<ll> ans(n + 1, inf);
    std::vector<bool> vis(n + 1);
    std::priority_queue<std::pair<ll, ll>> pq;
    ans[node] = 0;
    pq.push({0, node});
    while (!pq.empty()) {
      auto [d, node] = pq.top();
      d *= -1;
      pq.pop();
      if (vis[node]) {
        continue;
      }
      vis[node] = true;
      for (auto [ch, w, cur_i] : adj[node]) {
        if (ans[ch] > d + w) {
          ans[ch] = d + w;
          pq.push({-ans[ch], ch});
        }
      }
    }
    return ans;
  };

  auto sssp1 = sssp(1);
  auto ssspn = sssp(n);

  auto check = [&](ll x) {
    std::vector<std::vector<To>> new_adj(n + 1);
    for (ll i = 0; i < m; ++i) {
      auto [u, v, w] = edges[i];
      if (sssp1[u] + w + ssspn[v] <= x or sssp1[v] + w + ssspn[u] <= x) {
        new_adj[u].push_back({v, w, i});
        new_adj[v].push_back({u, w, i});
      }
    }
    std::vector<bool> is_bridge(m), vis(n + 1), enc(n + 1);
    enc[n] = true;
    std::vector<ll> low(n + 1), tin(n + 1);
    ll timer = 0;
    std::function<void(ll, ll)> dfs;
    dfs = [&](ll node, ll par) {
      if (vis[node]) {
        return;
      }
      vis[node] = true;
      tin[node] = timer++;
      low[node] = tin[node];
      for (auto &[ch, w, i] : new_adj[node]) {
        if (ch == par) {
          continue;
        }
        if (!vis[ch]) {
          dfs(ch, node);
          enc[node] = enc[node] || enc[ch];
        }
        is_bridge[i] = low[ch] > tin[node] and enc[ch];
        low[node] = std::min(low[node], low[ch]);
      }
    };
    dfs(1, 0);
    ll worst_road = edges[m - 1].w;
    for (ll i = m - 2; i >= 0; --i) {
      auto [u, v, w] = edges[i];
      if (is_bridge[i] and
          std::min(sssp1[u] + ssspn[v], sssp1[v] + ssspn[u]) + w + worst_road >
              x) {
        return true;
      }
      worst_road = std::max(worst_road, edges[i].w);
    }
    return false;
  };

  ll s = sssp1[n], e = 1e15;
  while (s < e) {
    ll m = s + (e - s) / 2;
    if (check(m)) {
      s = m + 1;
    } else {
      e = m;
    }
  }
  std::cout << s << '\n';
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 5 ms 860 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 6 ms 860 KB Output is correct
12 Correct 6 ms 940 KB Output is correct
13 Correct 5 ms 860 KB Output is correct
14 Correct 5 ms 976 KB Output is correct
15 Correct 6 ms 860 KB Output is correct
16 Correct 5 ms 996 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1807 ms 74492 KB Output is correct
2 Correct 1612 ms 82332 KB Output is correct
3 Correct 1756 ms 80116 KB Output is correct
4 Correct 1777 ms 80964 KB Output is correct
5 Correct 1855 ms 80844 KB Output is correct
6 Correct 1819 ms 83012 KB Output is correct
7 Correct 1708 ms 83128 KB Output is correct
8 Correct 1831 ms 83056 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1925 ms 76728 KB Output is correct
2 Correct 1934 ms 82180 KB Output is correct
3 Correct 1636 ms 81956 KB Output is correct
4 Correct 1570 ms 83492 KB Output is correct
5 Correct 1723 ms 80948 KB Output is correct
6 Correct 1640 ms 81396 KB Output is correct
7 Correct 1706 ms 81756 KB Output is correct
8 Correct 1833 ms 82472 KB Output is correct

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2032 ms 86084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2032 ms 86084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 5 ms 860 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 6 ms 860 KB Output is correct
12 Correct 6 ms 940 KB Output is correct
13 Correct 5 ms 860 KB Output is correct
14 Correct 5 ms 976 KB Output is correct
15 Correct 6 ms 860 KB Output is correct
16 Correct 5 ms 996 KB Output is correct
17 Correct 1807 ms 74492 KB Output is correct
18 Correct 1612 ms 82332 KB Output is correct
19 Correct 1756 ms 80116 KB Output is correct
20 Correct 1777 ms 80964 KB Output is correct
21 Correct 1855 ms 80844 KB Output is correct
22 Correct 1819 ms 83012 KB Output is correct
23 Correct 1708 ms 83128 KB Output is correct
24 Correct 1831 ms 83056 KB Output is correct
25 Correct 1925 ms 76728 KB Output is correct
26 Correct 1934 ms 82180 KB Output is correct
27 Correct 1636 ms 81956 KB Output is correct
28 Correct 1570 ms 83492 KB Output is correct
29 Correct 1723 ms 80948 KB Output is correct
30 Correct 1640 ms 81396 KB Output is correct
31 Correct 1706 ms 81756 KB Output is correct
32 Correct 1833 ms 82472 KB Output is correct
33 Execution timed out 2032 ms 86084 KB Time limit exceeded
34 Halted 0 ms 0 KB -