oj.uz

Submission #629744

# Submission time Handle Problem Language Result Execution time Memory
629744 2022-08-15T03:13:25 Z dooompy Islands (IOI08_islands) C++17
100 / 100
 967 ms 131072 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

bitset<1000005> seen, inloop;

int nxt[1000005], cost[1000005];
vector<int> rev[1000005];

ll globmax = 0;

ll dfs_tree(int node) {
    ll ans = 0;
    seen[node] = true;
    for (auto newnode : rev[node]) {
        if (inloop[newnode]) continue;

        ll temp = dfs_tree(newnode);

        globmax = max(globmax, ans + temp + cost[newnode]);
        ans = max(ans, temp + cost[newnode]);
    }

    return ans;
}

int main() {
//    freopen("isl.in", "r", stdin); freopen("isl.out", "w", stdout);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        int j;
        cin >> j >> cost[i];
        nxt[i] = j;
        rev[j].push_back(i);
    }

    ll total = 0;

    for (int i = 1; i <= n; i++) {
        if (seen[i]) continue;

        int cur = i;

        while (!seen[cur]) {
            seen[cur] = true;
            cur = nxt[cur];
        }

        vector<int> loop;

        loop.push_back(cur);
        inloop[cur] = true;
        int temp = nxt[cur];

        ll totalsum = cost[cur];
        while (temp != cur) {
            loop.push_back(temp);
            inloop[temp] =true;
            totalsum += cost[temp];
            temp = nxt[temp];
        }

        ll ans = 0;

        ll cursum = 0;

        ll prevInMax = 0, prevOutMax = 0;

        for (int i = 0; i < loop.size(); i++) {
            globmax = 0;
            ll tree = dfs_tree(loop[i]);

            if (i > 0) {
                cursum += cost[loop[i-1]];
                ans = max({ans, tree + cursum + prevInMax, totalsum + prevOutMax - cursum + tree});
            }
            ans = max(ans, globmax);

            prevInMax = max(prevInMax, tree - cursum);
            prevOutMax = max(prevOutMax, tree + cursum);

        }

//        cout << ans << endl;
        total += ans;

    }

    cout << total << endl;

}

Compilation message

islands.cpp: In function 'int main()':
islands.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < loop.size(); i++) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23780 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 12 ms 23764 KB Output is correct
9 Correct 12 ms 23744 KB Output is correct
10 Correct 12 ms 23812 KB Output is correct
11 Correct 13 ms 23764 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23812 KB Output is correct
2 Correct 15 ms 23764 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 15 ms 23832 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24148 KB Output is correct
2 Correct 35 ms 24692 KB Output is correct
3 Correct 28 ms 24372 KB Output is correct
4 Correct 20 ms 24004 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 25092 KB Output is correct
2 Correct 83 ms 26788 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 29116 KB Output is correct
2 Correct 130 ms 33240 KB Output is correct
3 Correct 177 ms 31592 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 35692 KB Output is correct
2 Correct 289 ms 36768 KB Output is correct
3 Correct 304 ms 49016 KB Output is correct
4 Correct 441 ms 52608 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 614 ms 35760 KB Output is correct
2 Correct 829 ms 65224 KB Output is correct
3 Correct 491 ms 55884 KB Output is correct
4 Correct 628 ms 64484 KB Output is correct
5 Correct 590 ms 61936 KB Output is correct
6 Correct 958 ms 65572 KB Output is correct
7 Correct 670 ms 69632 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 774 ms 131072 KB Output is correct
2 Correct 705 ms 109780 KB Output is correct
3 Correct 669 ms 82724 KB Output is correct
4 Correct 681 ms 78088 KB Output is correct
5 Correct 629 ms 63880 KB Output is correct
6 Correct 598 ms 66380 KB Output is correct
7 Correct 967 ms 66120 KB Output is correct