Submission #629744

#	Time	Username	Problem	Language	Result	Execution time	Memory
629744		dooompy	Islands (IOI08_islands)	C++17	100 / 100	967 ms	131072 KiB

islands

#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 (stderr)

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 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10