Submission #407242

#	Time	Username	Problem	Language	Result	Execution time	Memory
407242		Aldas25	Islands (IOI08_islands)	C++14	60 / 100	2078 ms	131076 KiB

islands

#pragma GCC optimize("O2")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;

const int MAXN = 1000100, MAXK = 30;
//const ll MOD = 998244353;
const ll INF = 1e17;
const ld PI = asin(1) * 2;

int n;
vii adj[MAXN];
ll dp[MAXN][2];
bool inCycle[MAXN];
bool vis[MAXN];
stack<int> st;
vi cycle;
ll cycleWalkLen = 0;
ll enterD[MAXN];

void dfs1 (int v, int p = -1) {
    vis[v] = true;
    st.push(v);
    for (auto pp : adj[v]) {
        int u = pp.f;
        ll l = pp.s;
        if (u == p) {
            p = -1;
            continue;
        }
        if (!vis[u]) {
            enterD[u] = enterD[v] + l;
            dfs1(u, v);
        }
        else {
            if ((int)cycle.size() == 0) {
                cycleWalkLen = enterD[v] - enterD[u] + l;
                while (st.top() != u) {
                    cycle.pb(st.top());
                    //cout << "   pushing " << st.top();
                    st.pop();
                }
                cycle.pb(u);
            //    cout << "    pushing u = "<<u<< endl;
            }
        }
    }
    if(!st.empty()) st.pop();
}

ll mxPath = 0;

void dfs2(int v,int p = -1) {
    for (auto pp : adj[v]) {
        int u = pp.f;
        ll l = pp.s;
        if (inCycle[u] || u == p) continue;
        dfs2(u, v);
        ll cr = dp[u][0] + l;
        if (cr > dp[v][0]) {
            dp[v][1] = dp[v][0];
            dp[v][0] = cr;
        } else if (cr > dp[v][1]) {
            dp[v][1] = cr;
        }
    }
    mxPath = max(mxPath, dp[v][0] + dp[v][1]);
}

int to[MAXN]; ll toLen[MAXN];
ll pref[MAXN];

ll getW (int a, int b) {
    //cout << "               getW a = " << a <<" b = " << b << endl;
    //cout << "                  toA = " << to[a] << " toB = " << to[b] << endl;
    if (to[a] != b) swap(a,b);
    //cout << "                        b=" << b << "-> " << " a=" << a << "  to[b] = " << to[b] << " tolen[b] = " << toLen[b]
 //<< endl;
     return toLen[a];
}

int main()
{
    FAST_IO;

    cin >> n;
    FOR(i, 1, n) {
        int u; ll l; cin >> u >> l;
        to[i] = u; toLen[i] = l;
        adj[i].pb({u, l});
        adj[u].pb({i, l});
    }

    ll ans = 0;
    FOR(i, 1, n) {
        if (vis[i]) continue;
       // cout << " i = " << i << endl;
        cycle.clear();
        cycleWalkLen = 0;
        dfs1(i);
        int len = (int)cycle.size();
        for (int x : cycle) {
            inCycle[x] = true;
            //cout << "  incycle x=" << x << endl;
        }
        FOR(a, 1, len-1) {
            int v = cycle[a];
            int pr = cycle[a-1];
            pref[a] = pref[a-1] + getW (v, pr);
           // cout << "       pref[" << a << "] = " << pref[a] << endl;
           // cout << "          v = " << v << " pr = " << pr << " getw = " << getW(v,pr) << endl;
        }
        ll curMax = 0;
        //cout << "     cycleWalkLen = " << cycleWalkLen << endl;
        for (int x : cycle) {
            mxPath = 0;
            dfs2(x);
            curMax = max(curMax, mxPath);
            //cout << "     x = " << x << "   mxPath = " << mxPath << endl;
        }

        FOR(a, 0, len-1) FOR(b, a+1, len-1) {
            ll cr = dp[cycle[a]][0] + dp[cycle[b]][0];
            cr += max(pref[b] - pref[a], cycleWalkLen-pref[b]+pref[a]);
            curMax = max(curMax, cr);
            //cout << "     a = " << a << "  b = " << b << "  u=" << cycle[a] << " v=" << cycle[b] <<" cr=" << cr << endl;
        }

        ans += curMax;
    }

    cout << ans << "\n";

    return 0;
}

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10