Submission #301962

#	Time	Username	Problem	Language	Result	Execution time	Memory
301962		bortoz	Islands (IOI08_islands)	C++17	60 / 100	2069 ms	131076 KiB

islands

#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pc __builtin_popcount

constexpr int MAXN = 1 << 20;

vector<tuple<int, int, int>> grafo[MAXN];
pair<int, int> succ[MAXN];
int vis[MAXN];
bool cycle[MAXN];
pair<ll, ll> dist[MAXN];

bool dfs1(int v, int x) {
  if (vis[v] == 2) {
    return false;
  } else if (vis[v] == 1) {
    cycle[v] = true;
    return true;
  }
  vis[v] = 1;
  for (auto [u, w, z] : grafo[v]) {
    if (x == z) continue;
    if (dfs1(u, z)) {
      succ[v] = {u, w};
    } else {
      succ[u] = {v, w};
    }
  }
  vis[v] = 2;
  return succ[v].fi != 0;
}

void dfs2(int v) {
  for (auto [u, w, _] : grafo[v]) {
    if (cycle[u] || u == succ[v].fi) continue;
    dfs2(u);
    dist[v].fi = max({dist[v].fi, dist[u].fi, dist[v].se + dist[u].se + w});
    dist[v].se = max(dist[v].se, dist[u].se + w);
  }
}

int main() {
  ios::sync_with_stdio(false);

  int N;
  cin >> N;

  for (int i = 1; i <= N; i++) {
    int b, c;
    cin >> b >> c;
    grafo[i].emplace_back(b, c, i);
    grafo[b].emplace_back(i, c, i);
  }

  for (int i = 1; i <= N; i++) {
    if (vis[i] == 0) dfs1(i, 0);
    if (!cycle[i]) continue;
    for (int j = succ[i].fi; j != i; j = succ[j].fi) {
      cycle[j] = true;
    }
  }

  for (int i = 1; i <= N; i++) {
    if (cycle[i]) dfs2(i);
  }

  vector<pair<ll, int>> Q;
  Q.reserve(N);
  ll sum_res = 0;
  for (int i = 1; i <= N; i++) {
    if (!cycle[i] || vis[i] == 8) continue;
    Q.clear();
    ll res = 0;
    ll path = 0;
    for (int j = i, gen = 0; vis[j] != 4; j = succ[j].fi, ++gen) {
      vis[j] = 4;
      Q.emplace_back(path + dist[j].se, gen);
      path += succ[j].se;
      res = max(res, dist[j].fi);
    }
    make_heap(Q.begin(), Q.end());
    ll tot = path;
    for (int j = i, gen = 0; vis[j] != 8; j = succ[j].fi, ++gen) {
      vis[j] = 8;
      while (Q[0].se <= gen) {
        pop_heap(Q.begin(), Q.end());
        Q.pop_back();
      }
      res = max(res, Q[0].fi - path + tot + dist[j].se);
      Q.emplace_back(path + dist[j].se, MAXN);
      push_heap(Q.begin(), Q.end());
      path += succ[j].se;
    }
    sum_res += res;
  }

  cout << sum_res << endl;

  return 0;
}

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