Submission #114471

#	Time	Username	Problem	Language	Result	Execution time	Memory
114471		popovicirobert	Islands (IOI08_islands)	C++14	80 / 100	620 ms	131072 KiB

islands

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const ll INF = 1e18;

struct Edge {
    int nod, cst;
    int id;
};

vector < vector <Edge> > g;
vector <int> vis;
vector < pair <int, int> > cyc;

vector < pair <int, int> > stk;
vector <int> nodes;

void get_cyc(int nod, int id) {
    nodes.push_back(nod);
    vis[nod] = 1;
    for(auto it : g[nod]) {
        if(vis[it.nod] == 0) {
            stk.push_back({nod, it.cst});
            get_cyc(it.nod, it.id);
            stk.pop_back();
        }
        else if(vis[it.nod] == 1 && it.id != id) {
            int i = (int) stk.size() - 1;
            while(i >= 0 && stk[i].first != it.nod) {
                cyc.push_back(stk[i]);
                i--;
            }
            cyc.push_back(stk[i]);
            reverse(cyc.begin(), cyc.end());
            cyc.push_back({nod, it.cst});
        }
    }
    vis[nod] = 2;
}

vector <ll> dp1, dp2;

void dfs(int nod, ll &ans)  {
    vis[nod] = 1;
    for(auto it : g[nod]) {
        if(vis[it.nod] == 0) {
            dfs(it.nod, ans);
            ll cur = dp1[it.nod] + it.cst;
            if(dp1[nod] <= cur) {
                dp2[nod] = dp1[nod];
                dp1[nod] = cur;
            }
            else if(dp2[nod] <= cur) {
                dp2[nod] = cur;
            }
        }
    }
    ans = max(ans, dp1[nod] + dp2[nod]);
}


inline ll solve(int nod) {

    cyc.clear(), nodes.clear();
    get_cyc(nod, 0);

    for(auto it : nodes) {
        vis[it] = 0;
    }
    ll sum = 0;
    for(auto it : cyc) {
        vis[it.first] = 1;
        sum += it.second;
    }

    ll cur = 0, mx1 = -INF, mx2 = -INF, ans = 0;
    for(auto it : cyc) {
        dfs(it.first, ans);
        if(it.first != cyc[0].first) {
            ans = max(ans, max(mx1 + dp1[it.first] + cur, mx2 + dp1[it.first] - cur));
        }
        mx1 = max(mx1, dp1[it.first] - cur);
        mx2 = max(mx2, dp1[it.first] + cur + sum);
        cur += it.second;
    }

    return ans;

}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    g.resize(n + 1);
    for(i = 1; i <= n; i++) {
        int nod, cst;
        cin >> nod >> cst;
        g[i].push_back({nod, cst, i});
        g[nod].push_back({i, cst, i});
    }

    vis.resize(n + 1);
    dp1.resize(n + 1), dp2.resize(n + 1);

    ll ans = 0;
    for(i = 1; i <= n; i++) {
        if(vis[i] == 0) {
            ans += solve(i);
        }
    }

    cout << ans;

    //cin.close();
    //cout.close();
    return 0;
}

• 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: 0 / 10
• Subtask 9: 0 / 10