oj.uz

Submission #301962

# Submission time Handle Problem Language Result Execution time Memory
301962 2020-09-18T10:37:04 Z bortoz Islands (IOI08_islands) C++17
60 / 100
 2000 ms 131076 KB 
#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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24960 KB Output is correct
2 Correct 19 ms 24960 KB Output is correct
3 Correct 19 ms 25088 KB Output is correct
4 Correct 19 ms 25088 KB Output is correct
5 Correct 18 ms 24960 KB Output is correct
6 Correct 18 ms 24960 KB Output is correct
7 Correct 18 ms 24960 KB Output is correct
8 Correct 19 ms 24960 KB Output is correct
9 Correct 18 ms 24960 KB Output is correct
10 Correct 18 ms 24960 KB Output is correct
11 Correct 18 ms 24960 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 25088 KB Output is correct
2 Correct 19 ms 25088 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 25216 KB Output is correct
2 Correct 40 ms 25592 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 26488 KB Output is correct
2 Correct 1583 ms 29720 KB Output is correct
3 Correct 30 ms 26744 KB Output is correct
4 Correct 24 ms 25856 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1269 ms 31640 KB Output is correct
2 Correct 1395 ms 34680 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1893 ms 43624 KB Output is correct
2 Execution timed out 2069 ms 41592 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 50232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 95368 KB Output is correct
2 Execution timed out 2056 ms 131072 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 419 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -