Submission #510215

#	Time	Username	Problem	Language	Result	Execution time	Memory
510215		BERNARB01	Islands (IOI08_islands)	C++17	15 / 100	2057 ms	131076 KiB

islands

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < n; i++) {
    int to, w;
    cin >> to >> w;
    --to;
    g[i].emplace_back(to, w);
    g[to].emplace_back(i, w);
  }

  vector<int> vis(n, 0);
  vector<int> nm;
  function<void(int)> mark_comp_vis = [&](int v) {
    vis[v] = 1;
    nm.push_back(v);
    for (auto [u, w] : g[v]) {
      if (vis[u]) {
        continue;
      }
      mark_comp_vis(u);
    }
  };

  vector<int> cyc;
  vector<int> stk;
  function<bool(int, int)> get_cyc = [&](int v, int pr) {
    stk.push_back(v);
    vis[v] = 1;
    int ccc = 0;
    for (auto [u, w] : g[v]) {
      ccc += (u == pr);
    }
    if (ccc == (int) g[v].size()) {
      while (!stk.empty()) {
        cyc.push_back(stk.back());
        if (stk.back() == pr) {
          break;
        }
        stk.pop_back();
      }
      return true;
    }
    for (auto [u, w] : g[v]) {
      if (u == pr) {
        continue;
      }
      if (vis[u]) {
        while (!stk.empty()) {
          cyc.push_back(stk.back());
          if (stk.back() == u) {
            break;
          }
          stk.pop_back();
        }
        return true;
      }
      if (get_cyc(u, v)) {
        return true;
      }
    }
    stk.pop_back();
    return false;
  };

  vector<long long> d(n);
  function<void(int, int)> calc_dists = [&](int v, int pr) {
    d[v] = 0;
    for (auto [u, w] : g[v]) {
      if (u == pr || vis[u]) {
        continue;
      }
      d[v] = max(d[v], w + d[u]);
      calc_dists(u, v);
    }
  };

  long long res = 0;
  for (int i = 0; i < n; i++) {
    if (!vis[i]) {
      nm.clear();
      mark_comp_vis(i);
      for (int v : nm) {
        vis[v] = 0;
      }
      cyc.clear();
      stk.clear();
      get_cyc(i, -1);
      for (int v : nm) {
        vis[v] = 0;
      }
      for (int v : cyc) {
        vis[v] = 1;
      }
      long long ans = 0;
      for (int v : cyc) {
        calc_dists(v, -1);
      }
      long long cyclen = 0;
      for (int v : cyc) {
        for (auto [u, w] : g[v]) {
          if (vis[u]) {
            cyclen += w;
          }
        }
      }
      cyclen >>= 1;
      for (int v : cyc) {
        for (auto [u, w] : g[v]) {
          if (vis[u]) {
            ans = max(ans, d[v] + cyclen - w);
          }
        }
      }
      for (int k = 1; k < (int) cyc.size(); k++) {
        int v = cyc[k];
        long long dvu = 0;
        for (int j = k - 1; j >= 0; j--) {
          for (auto [u, w] : g[v]) {
            if (u == cyc[j]) {
              dvu += w;
              break;
            }
          }
          ans = max(ans, d[v] + d[cyc[j]] + max(dvu, cyclen - dvu));
        }
      }
      res += ans;
      for (int v : nm) {
        vis[v] = 1;
      }
    }
  }
  cout << res << '\n';
  return 0;
}

• Subtask 1: 15 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10