제출 #585597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585597		tranxuanbach	Islands (IOI08_islands)	C++17	60 / 100	2083 ms	131072 KiB

islands

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 1e6 + 5, LN = 20;
const ll infll = (ll)1e18 + 7;

int n;
int a[N], b[N];
vpii adj[N];

ll ans;

int vis[N], incycle[N];

void dfs_incycle(int u){
    vis[u] = 2;
    if (vis[a[u]] == 1){

    }
    else if (vis[a[u]] == 2){
        int v = u;
        do{
            incycle[v] = 1;
            v = a[v];
        } while (v != u);
    }
    else{
        dfs_incycle(a[u]);
    }
    vis[u] = 1;
}

ll chain[N];

pair <ll, int> dfs_farthest(int r, int u, int p){
    pair <ll, int> ans = make_pair(0ll, u);
    for (auto &[v, w]: adj[u]){
        if ((incycle[v] and v != r) or v == p){
            continue;
        }
        auto tans = dfs_farthest(r, v, u); tans.fi += w;
        ans = max(ans, tans);
    }
    return ans;
}

ll dfs_dist(int u, int p){
    ll ans = 0;
    for (auto &[v, w]: adj[u]){
        if (incycle[v] or v == p){
            continue;
        }
        ans = max(ans, dfs_dist(v, u) + w);
    }
    return ans;
}

int node[N]; ll prefdist[N];

ll c[N];
ll mxprefc[N], mxsuffc[N];
// ll mxc[LN][N];

// ll query(int l, int r, ll mxa[][N]){
//     if (l > r){
//         return -infll;
//     }
//     int z = __lg(r - l + 1);
//     return max(mxa[z][l], mxa[z][r - (1 << z) + 1]);
// }

int ldq, rdq, dq[N];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n;
    ForE(u, 1, n){
        int v, w; cin >> v >> w;
        a[u] = v; b[u] = w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    memset(vis, 0, sizeof(vis));
    ForE(u, 1, n){
        if (vis[u] == 0){
            dfs_incycle(u);
        }
    }

    memset(vis, 0, sizeof(vis));
    ForE(u, 1, n){
        if (vis[u] == 0 and incycle[u] == 1){
            chain[u] = dfs_dist(u, u);
        }
    }

    memset(vis, 0, sizeof(vis));
    ForE(u, 1, n){
        if (vis[u] == 0 and incycle[u] == 1){
            ll tans = 0;
            int len = 0; ll dist = 0;
            {
                int v = u, i = 0; ll d = 0;
                do{
                    {
                        int d1 = dfs_farthest(v, v, v).se;
                        tans = max(tans, dfs_farthest(v, d1, d1).fi);
                    }
                    vis[v] = 1;
                    node[i] = v;
                    prefdist[i] = d;
                    c[i] = chain[v] - prefdist[i];
                    d += b[v];
                    v = a[v];
                    i++;
                } while (v != u);
                len = i; dist = d;
            }

            // cout << "cycle " << u << endl;
            // For(i, 0, len){
            //     cout << node[i] << ' ' << prefdist[i] << ' ' << c[i] << endl;
            // }
            
            // For(i, 0, len){
            //     mxc[0][i] = c[i];
            // }
            // For(j, 1, LN){
            //     For(i, 0, len - (1 << j) + 1){
            //         mxc[j][i] = max(mxc[j - 1][i], mxc[j - 1][i + (1 << (j - 1))]);
            //     }
            // }
            For(i, 0, len){
                mxprefc[i] = max(i == 0 ? -infll : mxprefc[i - 1], c[i]);
            }
            FordE(i, len - 1, 0){
                mxsuffc[i] = max(i == len - 1 ? -infll : mxsuffc[i + 1], c[i]);
            }
            ldq = 0; rdq = 0;

            int j = 0; ll hdist = 0;
            For(i, 0, len){
                if (j < i){
                    j = i;
                    hdist = 0;
                    ldq = 0; rdq = 0;
                }
                while ((hdist + b[node[j]]) * 2 <= dist){
                    hdist += b[node[j]];
                    j++; if (j == len) j = 0;
                    while (rdq > ldq and c[dq[rdq - 1]] <= c[j]){
                        rdq--;
                    }
                    rdq++; dq[rdq - 1] = j;
                }
                // cout << "i j " << i << ' ' << j << endl;
                if (j >= i){
                    tans = max(tans, chain[node[i]] + dist + prefdist[i] + /*query(i + 1, j, mxc)*/ (ldq == rdq ? -infll : c[dq[ldq]]));
                }
                else{
                    tans = max(tans, chain[node[i]] + dist + prefdist[i] + /*query(i + 1, len - 1, mxc)*/ (i == len - 1 ? -infll : mxsuffc[i + 1]));
                    tans = max(tans, chain[node[i]] + prefdist[i] + /*query(0, j, mxc)*/ mxprefc[j]);
                }
                // cout << "tans " << tans << endl;
                hdist -= b[node[i]];
                if (dq[ldq] == i + 1){
                    ldq++;
                }
            }
            ans += tans;
        }
    }

    cout << ans << endl;
}

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

• 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