Submission #510227

#	Time	Username	Problem	Language	Result	Execution time	Memory
510227		BERNARB01	Islands (IOI08_islands)	C++17	18 / 100	1966 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, long long>>> g(n);
  map<pair<int, int>, int> mp;
  for (int i = 0; i < n; i++) {
    long long to, w;
    cin >> to >> w;
    --to;
    mp[{i, to}] = 1;
    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;
    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);
    }
  };

  int _f;
  long long _dia;
  function<void(int, int, long long)> get_dia = [&](int v, int pr, long long dph) {
    if (dph > _dia) {
      _f = v;
      _dia = dph;
    }
    for (auto [u, w] : g[v]) {
      if (u == pr || vis[u]) {
        continue;
      }
      get_dia(u, v, dph + w);
    }
  };

  long long res = 0;
  for (int i = 0; i < n; i++) {
    if (vis[i]) {
      continue;
    }
    nm.clear();
    mark_comp_vis(i);
    for (int v : nm) {
      vis[v] = 0;
    }
    cyc.clear();
    stk.clear();
    get_cyc(i, -1);
    if (cyc.size() == 1) {
      for (auto [u, w] : g[cyc[0]]) {
        if (mp.count(make_pair(cyc[0], u)) && mp.count(make_pair(u, cyc[0]))) {
          cyc.push_back(u);
          break;
        }
      }
    }
    for (int v : nm) {
      vis[v] = 0;
    }
    for (int v : cyc) {
      vis[v] = 1;
    }
    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;
    long long ans = 0;
    for (int v : cyc) {
      _dia = 0; _f = v;
      get_dia(v, -1, 0);
      get_dia(_f, -1, 0);
      ans = max(ans, _dia);
      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: 18 / 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