Submission #301960

#	Time	Username	Problem	Language	Result	Execution time	Memory
301960		bortoz	Islands (IOI08_islands)	C++17	0 / 100	57 ms	50552 KiB

islands

#pragma GCC optimize("O3")
#include <fcntl.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pc __builtin_popcount

class FastReader {
 private:
  char* data;
  size_t offset;
  size_t length;

 public:
  FastReader(const char* fileName) {
    int fd = open(fileName, O_RDONLY);
    struct stat sb;
    fstat(fd, &sb);
    length = (size_t)sb.st_size;
    data = (char*)mmap(nullptr, length, PROT_READ, MAP_PRIVATE, fd, 0);
    offset = 0;
    close(fd);
  }

  ~FastReader() { munmap(data, length); }

  template <typename T,
            typename enable_if<is_unsigned<T>::value, int>::type = 0>
  friend FastReader& operator>>(FastReader& fr, T& val) {
    for (; fr.data[fr.offset] < '0'; fr.offset++)
      ;
    for (val = 0; fr.data[fr.offset] >= '0'; fr.offset++) {
      val = val * 10 + (fr.data[fr.offset] - '0');
    }
    return fr;
  }

  template <typename T, typename enable_if<is_signed<T>::value, int>::type = 0>
  friend FastReader& operator>>(FastReader& fr, T& val) {
    for (; fr.data[fr.offset] < '-'; fr.offset++)
      ;
    bool neg = fr.data[fr.offset] == '-';
    if (neg) fr.offset++;
    for (val = 0; fr.data[fr.offset] >= '0'; fr.offset++) {
      val = val * 10 + (fr.data[fr.offset] - '0');
    }
    if (neg) val = -val;
    return fr;
  }

  friend FastReader& operator>>(FastReader& fr, char& val) {
    val = fr.data[fr.offset++];
    return fr;
  }

  friend FastReader& operator>>(FastReader& fr, string& val) {
    size_t sz = 0;
    for (; fr.data[fr.offset] <= ' '; fr.offset++)
      ;
    for (; fr.data[fr.offset] > ' '; fr.offset++)
      sz++;
    val.assign(string(fr.data + fr.offset, fr.data + fr.offset + sz));
    fr.offset += sz;
    return fr;
  }
};

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);

  FastReader cin("input.txt");
  ofstream cout("output.txt");

  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: 0 / 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