oj.uz

Submission #1082927

# Submission time Handle Problem Language Result Execution time Memory
1082927 2024-09-02T06:23:37 Z avighna Aesthetic (NOI20_aesthetic) C++17
51 / 100
 2000 ms 65052 KB 
#include <bits/stdc++.h>

typedef long long ll;

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

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<ll> roads(m);
  std::vector<std::pair<ll, ll>> 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});
    roads[i] = w;
    edges.push_back({u, v});
  }

  if (m == n - 1) {
    // there will only be one path
    std::set<ll> edges;
    std::function<bool(ll, ll)> dfs;
    ll def = 0;
    dfs = [&](ll node, ll par) {
      if (node == n) {
        return true;
      }
      for (auto &[ch, w, i] : adj[node]) {
        if (ch == par) {
          continue;
        }
        if (dfs(ch, node)) {
          edges.insert(i);
          def += w;
          return true;
        }
      }
      return false;
    };
    dfs(1, 0);

    ll ans = def;
    ll worst_road = roads[m - 1];
    for (ll i = m - 2; i >= 0; --i) {
      if (edges.count(i)) {
        ans = std::max(ans, def + worst_road);
      }
      worst_road = std::max(worst_road, roads[i]);
    }
    std::cout << ans << '\n';

    return 0;
  }

  if (m == n) {
    // find the cycle
    std::vector<std::pair<ll, ll>> up(n + 1);
    std::function<void(ll, ll)> dfs;
    std::vector<bool> vis(n + 1);
    bool found = false;
    ll begin_node = -1;
    dfs = [&](ll node, ll par) {
      if (found) {
        return;
      }
      if (vis[node]) {
        return;
      }
      vis[node] = true;
      for (auto &[ch, w, i] : adj[node]) {
        if (ch == par) {
          continue;
        }
        up[ch] = {node, i};
        if (vis[ch]) {
          begin_node = node;
          found = true;
          return;
        }
        dfs(ch, node);
        if (found) {
          return;
        }
      };
    };
    dfs(1, 0);
    std::set<ll> cycle_edegs;
    ll tot_cyc_wt = 0;
    if (found) {
      vis.assign(n + 1, false);
      while (!vis[begin_node]) {
        vis[begin_node] = true;
        cycle_edegs.insert(up[begin_node].second);
        tot_cyc_wt += roads[up[begin_node].second];
        begin_node = up[begin_node].first;
      }
    }

    std::set<ll> shortest_path_edges;
    ll shortest_cyc_wt = 0;
    ll def = 0;
    auto sssp = [&]() {
      std::vector<ll> ans(n + 1, inf);
      std::vector<bool> vis(n + 1);
      std::vector<std::pair<ll, ll>> up(n + 1);
      std::priority_queue<std::pair<ll, ll>> pq;
      pq.push({0, 1});
      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) {
            up[ch] = {node, cur_i};
            ans[ch] = d + w;
            pq.push({-ans[ch], ch});
          }
        }
      }
      def = ans[n];
      ll end = n;
      while (end != 1) {
        shortest_path_edges.insert(up[end].second);
        if (cycle_edegs.count(up[end].second)) {
          shortest_cyc_wt += roads[up[end].second];
        }
        end = up[end].first;
      }
    };
    sssp();

    ll ans = def;
    ll worst_road = roads[m - 1];
    for (ll i = m - 2; i >= 0; --i) {
      if (shortest_path_edges.count(i)) {
        if (cycle_edegs.count(i)) {
          ans = std::max(ans, std::min(def + worst_road,
                                       def - 2 * shortest_cyc_wt + tot_cyc_wt));
        } else {
          ans = std::max(ans, def + worst_road);
        }
      }
      worst_road = std::max(worst_road, roads[i]);
    }
    std::cout << ans << '\n';

    return 0;
  };

  if (*std::max_element(roads.begin(), roads.end()) == 1 and
      *std::min_element(roads.begin(), roads.end()) == 1) {
    // w_i = 1
    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);
    std::set<ll> special_edges;
    std::map<std::pair<ll, ll>, ll> edge_starts;
    for (ll i = 0; i < edges.size(); ++i) {
      auto [u, v] = edges[i];
      if (std::min(sssp1[u] + 1 + ssspn[v], sssp1[v] + 1 + ssspn[u]) ==
          sssp1[n]) {
        special_edges.insert(i);
        if (sssp1[u] + 1 + ssspn[v] == sssp1[n]) {
          edge_starts[{sssp1[u], ssspn[v]}]++;
        } else {
          edge_starts[{sssp1[v], ssspn[u]}]++;
        }
      }
    }

    ll ans = sssp1[n];
    for (ll i = 0; i <= m - 2; ++i) {
      auto [u, v] = edges[i];
      if (special_edges.count(i) and
          ((edge_starts[{sssp1[u], ssspn[v]}] == 1 and
            sssp1[u] + 1 + ssspn[v] == sssp1[n]) or
           (edge_starts[{sssp1[v], sssp1[u]}] == 1 and
            sssp1[v] + 1 + ssspn[u]))) {
        ans = std::max(ans, sssp1[n] + 1);
      }
    }
    std::cout << ans << '\n';
    return 0;
  }

  // exclude edge i
  auto sssp = [&](ll i, ll add) {
    std::vector<ll> ans(n + 1, inf);
    std::vector<bool> vis(n + 1);
    std::priority_queue<std::pair<ll, ll>> pq;
    pq.push({0, 1});
    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 (cur_i == i) {
          w += add;
        }
        if (ans[ch] > d + w) {
          ans[ch] = d + w;
          pq.push({-ans[ch], ch});
        }
      }
    }
    return ans;
  };

  ll def = sssp(-1, 0)[n];
  ll ans = def;
  ll worst_road = roads[m - 1];
  for (ll i = m - 2; i >= 0; --i) {
    ans = std::max(ans, sssp(i, worst_road)[n]);
    worst_road = std::max(worst_road, roads[i]);
  }
  std::cout << ans << '\n';
}

Compilation message

Aesthetic.cpp: In function 'int main()':
Aesthetic.cpp:195:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |     for (ll i = 0; i < edges.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 0 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 1 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 0 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 1 ms 348 KB Output is correct
9 Correct 210 ms 604 KB Output is correct
10 Correct 198 ms 604 KB Output is correct
11 Correct 136 ms 604 KB Output is correct
12 Correct 147 ms 604 KB Output is correct
13 Correct 72 ms 604 KB Output is correct
14 Correct 69 ms 848 KB Output is correct
15 Correct 65 ms 600 KB Output is correct
16 Correct 67 ms 600 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 43424 KB Output is correct
2 Correct 153 ms 41836 KB Output is correct
3 Correct 151 ms 41652 KB Output is correct
4 Correct 136 ms 42676 KB Output is correct
5 Correct 136 ms 41656 KB Output is correct
6 Correct 144 ms 42156 KB Output is correct
7 Correct 146 ms 41908 KB Output is correct
8 Correct 139 ms 42236 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 53932 KB Output is correct
2 Correct 197 ms 53240 KB Output is correct
3 Correct 234 ms 53116 KB Output is correct
4 Correct 210 ms 53936 KB Output is correct
5 Correct 235 ms 52912 KB Output is correct
6 Correct 199 ms 53532 KB Output is correct
7 Correct 189 ms 53032 KB Output is correct
8 Correct 222 ms 54704 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 43184 KB Output is correct
2 Correct 142 ms 42672 KB Output is correct
3 Correct 243 ms 49644 KB Output is correct
4 Correct 231 ms 50512 KB Output is correct
5 Correct 242 ms 50864 KB Output is correct
6 Correct 247 ms 49588 KB Output is correct
7 Correct 234 ms 50872 KB Output is correct
8 Correct 225 ms 50316 KB Output is correct
9 Correct 245 ms 50096 KB Output is correct
10 Correct 239 ms 51376 KB Output is correct
11 Correct 240 ms 50096 KB Output is correct
12 Correct 215 ms 45056 KB Output is correct
13 Correct 239 ms 51376 KB Output is correct
14 Correct 136 ms 54188 KB Output is correct
15 Correct 151 ms 65052 KB Output is correct
16 Correct 211 ms 43648 KB Output is correct
17 Correct 222 ms 44012 KB Output is correct
18 Correct 233 ms 44508 KB Output is correct
19 Correct 148 ms 40880 KB Output is correct
20 Correct 162 ms 40928 KB Output is correct
21 Correct 161 ms 42676 KB Output is correct
22 Correct 142 ms 41136 KB Output is correct

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 43184 KB Output is correct
2 Correct 142 ms 42672 KB Output is correct
3 Correct 243 ms 49644 KB Output is correct
4 Correct 231 ms 50512 KB Output is correct
5 Correct 242 ms 50864 KB Output is correct
6 Correct 247 ms 49588 KB Output is correct
7 Correct 234 ms 50872 KB Output is correct
8 Correct 225 ms 50316 KB Output is correct
9 Correct 245 ms 50096 KB Output is correct
10 Correct 239 ms 51376 KB Output is correct
11 Correct 240 ms 50096 KB Output is correct
12 Correct 215 ms 45056 KB Output is correct
13 Correct 239 ms 51376 KB Output is correct
14 Correct 136 ms 54188 KB Output is correct
15 Correct 151 ms 65052 KB Output is correct
16 Correct 211 ms 43648 KB Output is correct
17 Correct 222 ms 44012 KB Output is correct
18 Correct 233 ms 44508 KB Output is correct
19 Correct 148 ms 40880 KB Output is correct
20 Correct 162 ms 40928 KB Output is correct
21 Correct 161 ms 42676 KB Output is correct
22 Correct 142 ms 41136 KB Output is correct
23 Execution timed out 2060 ms 44276 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 0 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 1 ms 348 KB Output is correct
9 Correct 210 ms 604 KB Output is correct
10 Correct 198 ms 604 KB Output is correct
11 Correct 136 ms 604 KB Output is correct
12 Correct 147 ms 604 KB Output is correct
13 Correct 72 ms 604 KB Output is correct
14 Correct 69 ms 848 KB Output is correct
15 Correct 65 ms 600 KB Output is correct
16 Correct 67 ms 600 KB Output is correct
17 Correct 172 ms 43424 KB Output is correct
18 Correct 153 ms 41836 KB Output is correct
19 Correct 151 ms 41652 KB Output is correct
20 Correct 136 ms 42676 KB Output is correct
21 Correct 136 ms 41656 KB Output is correct
22 Correct 144 ms 42156 KB Output is correct
23 Correct 146 ms 41908 KB Output is correct
24 Correct 139 ms 42236 KB Output is correct
25 Correct 262 ms 53932 KB Output is correct
26 Correct 197 ms 53240 KB Output is correct
27 Correct 234 ms 53116 KB Output is correct
28 Correct 210 ms 53936 KB Output is correct
29 Correct 235 ms 52912 KB Output is correct
30 Correct 199 ms 53532 KB Output is correct
31 Correct 189 ms 53032 KB Output is correct
32 Correct 222 ms 54704 KB Output is correct
33 Correct 254 ms 43184 KB Output is correct
34 Correct 142 ms 42672 KB Output is correct
35 Correct 243 ms 49644 KB Output is correct
36 Correct 231 ms 50512 KB Output is correct
37 Correct 242 ms 50864 KB Output is correct
38 Correct 247 ms 49588 KB Output is correct
39 Correct 234 ms 50872 KB Output is correct
40 Correct 225 ms 50316 KB Output is correct
41 Correct 245 ms 50096 KB Output is correct
42 Correct 239 ms 51376 KB Output is correct
43 Correct 240 ms 50096 KB Output is correct
44 Correct 215 ms 45056 KB Output is correct
45 Correct 239 ms 51376 KB Output is correct
46 Correct 136 ms 54188 KB Output is correct
47 Correct 151 ms 65052 KB Output is correct
48 Correct 211 ms 43648 KB Output is correct
49 Correct 222 ms 44012 KB Output is correct
50 Correct 233 ms 44508 KB Output is correct
51 Correct 148 ms 40880 KB Output is correct
52 Correct 162 ms 40928 KB Output is correct
53 Correct 161 ms 42676 KB Output is correct
54 Correct 142 ms 41136 KB Output is correct
55 Execution timed out 2060 ms 44276 KB Time limit exceeded
56 Halted 0 ms 0 KB -