oj.uz

Submission #510227

# Submission time Handle Problem Language Result Execution time Memory
510227 2022-01-14T20:08:59 Z BERNARB01 Islands (IOI08_islands) C++17
18 / 100
 1966 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, long long>>> g(n);
  map<pair<int, int>, int> mp;
  for (int i = 0; i < n; i++) {
    long long to, w;
    cin >> to >> w;
    --to;
    mp[{i, to}] = 1;
    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;
    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);
    }
  };

  int _f;
  long long _dia;
  function<void(int, int, long long)> get_dia = [&](int v, int pr, long long dph) {
    if (dph > _dia) {
      _f = v;
      _dia = dph;
    }
    for (auto [u, w] : g[v]) {
      if (u == pr || vis[u]) {
        continue;
      }
      get_dia(u, v, dph + w);
    }
  };

  long long res = 0;
  for (int i = 0; i < n; i++) {
    if (vis[i]) {
      continue;
    }
    nm.clear();
    mark_comp_vis(i);
    for (int v : nm) {
      vis[v] = 0;
    }
    cyc.clear();
    stk.clear();
    get_cyc(i, -1);
    if (cyc.size() == 1) {
      for (auto [u, w] : g[cyc[0]]) {
        if (mp.count(make_pair(cyc[0], u)) && mp.count(make_pair(u, cyc[0]))) {
          cyc.push_back(u);
          break;
        }
      }
    }
    for (int v : nm) {
      vis[v] = 0;
    }
    for (int v : cyc) {
      vis[v] = 1;
    }
    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;
    long long ans = 0;
    for (int v : cyc) {
      _dia = 0; _f = v;
      get_dia(v, -1, 0);
      get_dia(_f, -1, 0);
      ans = max(ans, _dia);
      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
18.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
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 Correct 0 ms 204 KB Output is correct
8 Incorrect 0 ms 204 KB Output isn't correct
9 Correct 0 ms 204 KB Output is correct
10 Incorrect 1 ms 204 KB Output isn't correct
11 Correct 0 ms 332 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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