oj.uz

Submission #1020329

# Submission time Handle Problem Language Result Execution time Memory
1020329 2024-07-11T23:47:30 Z aaaaaarroz Islands (IOI08_islands) C++17
100 / 100
 184 ms 52308 KB 
    #include <bits/stdc++.h>
     
    using namespace std;
    using ll = long long;
     
    const int MxN = 1000010;
     
    pair<int, ll> nxt[MxN];
    bitset<MxN> cycle;
    int in[MxN];
    queue<int> q;
    ll dist[MxN], dp[MxN];
     
    signed main(int argc, char *argv[]) {
      cin.tie(nullptr)->ios::sync_with_stdio(false);
      int n;
      cin >> n;
      for(int i=1; i<=n; ++i) {
        cin >> nxt[i].first >> nxt[i].second;
        in[nxt[i].first]++;
      }
      for(int i=1; i<=n; ++i) {
        if(in[i] != 0) {
          continue;
        }
        q.emplace(i);
      }
      while(!q.empty()) {
        int u = q.front(); q.pop();
        int v = nxt[u].first;
        ll w = nxt[u].second;
        dp[v] = max({dp[u], dp[v], dist[v] + dist[u] + w});
        dist[v] = max(dist[v], dist[u] + w);
        if (--in[v] == 0) {
            q.emplace(v);
        }
      }
    #ifdef ICY
      for(int i=1; i<=n; ++i) {
        cerr << "D: " << dp[i] << " " << dist[i] << "\n";
      }
    #endif
      auto calc = [&](int pos) {
        int cur_pos = pos;
        cur_pos = nxt[pos].first;
        ll cur_dist = nxt[pos].second;
        ll with = dist[pos];
        ll without = dist[pos];
        ll max_dp_with = dp[pos];
        ll max_dp_without = -1e18 - 100ll;
    #ifdef ICY
        cerr << "PRE: " << max_dp_with << " " << max_dp_without << " " << cur_dist << "\n";
    #endif
        while(cur_pos != pos) {
          in[cur_pos] = 0;
          max_dp_with = max({max_dp_with, dp[cur_pos], dist[cur_pos] + cur_dist + with});
          max_dp_without = max(max_dp_without, dist[cur_pos] - cur_dist + without);
          with = max(with, dist[cur_pos] - cur_dist);
          without = max(without, dist[cur_pos] + cur_dist);
          cur_dist += nxt[cur_pos].second;
          cur_pos = nxt[cur_pos].first;
    #ifdef ICY
          cerr << "A: " << max_dp_with << " " << max_dp_without << "\n";
    #endif
       }
        return max(max_dp_without + cur_dist, max_dp_with);
      };
      ll answer = 0ll;
      for(int i=1; i<=n; ++i) {
        if(in[i] == 0) {
          continue;
        }
    #ifdef ICY
        cerr << "X: " << i << "\n";
    #endif
        answer += calc(i);
      }
      cout << answer << "\n";
      return 0;
    }

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 600 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1116 KB Output is correct
2 Correct 5 ms 2040 KB Output is correct
3 Correct 3 ms 1372 KB Output is correct
4 Correct 2 ms 860 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2908 KB Output is correct
2 Correct 12 ms 4956 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10324 KB Output is correct
2 Correct 34 ms 8528 KB Output is correct
3 Correct 35 ms 13336 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 19028 KB Output is correct
2 Correct 66 ms 24660 KB Output is correct
3 Correct 63 ms 19024 KB Output is correct
4 Correct 96 ms 33112 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 35664 KB Output is correct
2 Correct 147 ms 43088 KB Output is correct
3 Correct 105 ms 39408 KB Output is correct
4 Correct 135 ms 49992 KB Output is correct
5 Correct 128 ms 49724 KB Output is correct
6 Correct 178 ms 50768 KB Output is correct
7 Correct 137 ms 52308 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 50936 KB Output is correct
2 Correct 142 ms 51040 KB Output is correct
3 Correct 124 ms 35408 KB Output is correct
4 Correct 120 ms 34896 KB Output is correct
5 Correct 159 ms 50260 KB Output is correct
6 Correct 135 ms 49452 KB Output is correct
7 Correct 184 ms 51212 KB Output is correct