oj.uz

Submission #510215

# Submission time Handle Problem Language Result Execution time Memory
510215 2022-01-14T19:46:41 Z BERNARB01 Islands (IOI08_islands) C++17
15 / 100
 2000 ms 131076 KB 
#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, int>>> g(n);
  for (int i = 0; i < n; i++) {
    int to, w;
    cin >> to >> w;
    --to;
    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;
    int ccc = 0;
    for (auto [u, w] : g[v]) {
      ccc += (u == pr);
    }
    if (ccc == (int) g[v].size()) {
      while (!stk.empty()) {
        cyc.push_back(stk.back());
        if (stk.back() == pr) {
          break;
        }
        stk.pop_back();
      }
      return true;
    }
    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);
    }
  };

  long long res = 0;
  for (int i = 0; i < n; i++) {
    if (!vis[i]) {
      nm.clear();
      mark_comp_vis(i);
      for (int v : nm) {
        vis[v] = 0;
      }
      cyc.clear();
      stk.clear();
      get_cyc(i, -1);
      for (int v : nm) {
        vis[v] = 0;
      }
      for (int v : cyc) {
        vis[v] = 1;
      }
      long long ans = 0;
      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;
      for (int v : cyc) {
        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
15.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Runtime error 154 ms 131076 KB Execution killed with signal 9
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Incorrect 0 ms 204 KB Output isn't correct
6 Correct 0 ms 204 KB Output is correct
7 Incorrect 0 ms 232 KB Output isn't correct
8 Runtime error 120 ms 131076 KB Execution killed with signal 9
9 Correct 0 ms 204 KB Output is correct
10 Incorrect 0 ms 204 KB Output isn't correct
11 Correct 0 ms 204 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 6092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 283 ms 98124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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