oj.uz

Submission #301960

# Submission time Handle Problem Language Result Execution time Memory
301960 2020-09-18T10:36:20 Z bortoz Islands (IOI08_islands) C++17
0 / 100
 57 ms 50552 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 50424 KB Execution killed with signal 11
2 Runtime error 51 ms 50296 KB Execution killed with signal 11
3 Runtime error 51 ms 50424 KB Execution killed with signal 11
4 Runtime error 50 ms 50424 KB Execution killed with signal 11
5 Runtime error 50 ms 50360 KB Execution killed with signal 11
6 Runtime error 51 ms 50296 KB Execution killed with signal 11
7 Runtime error 57 ms 50352 KB Execution killed with signal 11
8 Runtime error 53 ms 50296 KB Execution killed with signal 11
9 Runtime error 50 ms 50552 KB Execution killed with signal 11
10 Runtime error 51 ms 50424 KB Execution killed with signal 11
11 Runtime error 51 ms 50296 KB Execution killed with signal 11

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 50296 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 50552 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 50300 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 50484 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 50296 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 51 ms 50296 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 50296 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 50424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -