Submission #1171904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171904		lopkus	Cheap flights (LMIO18_pigus_skrydziai)	C++20	53 / 100	778 ms	108908 KiB

pigus_skrydziai

#include <bits/stdc++.h>

#define int long long

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, m;
  std::cin >> n >> m;
  std::vector<std::pair<int,int64_t>> adj[n + 1];
  std::map<std::pair<int,int>, int64_t> cost;
  for(int i = 1; i <= m; i++) {
    int u, v, c;
    std::cin >> u >> v >> c;
    adj[u].push_back({v, c});
    adj[v].push_back({u, c});
    cost[{u, v}] = c;
    cost[{v, u}] = c;
  }
  int64_t ans = 0;
  for(int i = 1; i <= n; i++) {
    int64_t sum = 0;
    for(auto [y, c] : adj[i]) {
      sum += c;
    }
    ans = std::max(ans, sum);
  }
  std::vector<int> was(n + 1);
  std::vector<int> P(n + 1);
  std::vector<std::array<int64_t, 3>> back_edges;
  std::vector<int> in(n + 1);
  int tt = 1;
  std::function<void(int, int)> dfs = [&] (int u, int p) {
    was[u] = 1;
    P[u] = p;
    in[u] = tt++;
    for(auto [v, w] : adj[u]) {
      if(v == p) {
        continue;
      }
      if(was[v]) {
        back_edges.push_back({v, u, w});
      }
      else {
        dfs(v, u);
      }
    }
  };
  for(int i = 1; i <= n; i++) {
    if(!was[i]) {
      dfs(i, 0);
    }
  }
  for(auto [u, v, c] : back_edges) {
    if(in[u] < in[v]) {
      continue;
    }
    if(P[u] != 0 && P[P[u]] != 0 && P[P[u]] == v) {
      ans = std::max(ans, cost[{u, P[u]}] + cost[{P[u], v}] + c);
    }
  }
  std::cout << ans;
}

• Subtask 1: 12 / 12
• Subtask 2: 25 / 25
• Subtask 3: 16 / 16
• Subtask 4: 0 / 47