답안 #585569

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585569 2022-06-29T05:20:48 Z tranxuanbach Islands (IOI08_islands) C++17
54 / 100
334 ms 131072 KB
#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 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]);
}

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){
            {
                int d1 = dfs_farthest(u, u, u).se;
                ans = max(ans, dfs_farthest(u, d1, d1).fi);
            }
            chain[u] = dfs_dist(u, u);
        }
    }

    ll ans = 0;
    memset(vis, 0, sizeof(vis));
    ForE(u, 1, n){
        if (vis[u] == 0 and incycle[u] == 1){
            int len = 0; ll dist = 0;
            {
                int v = u, i = 0; ll d = 0;
                do{
                    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))]);
                }
            }

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

    cout << ans << endl;
}

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

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

--------------------------------------------------|
==================================================+
*/
# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 27732 KB Output is correct
2 Incorrect 14 ms 27732 KB Output isn't correct
3 Correct 15 ms 27820 KB Output is correct
4 Correct 15 ms 27724 KB Output is correct
5 Correct 14 ms 27784 KB Output is correct
6 Correct 14 ms 27732 KB Output is correct
7 Correct 16 ms 27752 KB Output is correct
8 Correct 15 ms 27696 KB Output is correct
9 Correct 14 ms 27764 KB Output is correct
10 Incorrect 17 ms 27728 KB Output isn't correct
11 Correct 15 ms 27800 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 27860 KB Output is correct
2 Correct 15 ms 27780 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 27928 KB Output is correct
2 Correct 17 ms 28276 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 29080 KB Output is correct
2 Correct 33 ms 32552 KB Output is correct
3 Correct 28 ms 29260 KB Output is correct
4 Incorrect 24 ms 28556 KB Output isn't correct
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 34376 KB Output is correct
2 Correct 45 ms 37420 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 44896 KB Output is correct
2 Correct 83 ms 53708 KB Output is correct
3 Correct 106 ms 72592 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 54788 KB Output is correct
2 Correct 174 ms 98656 KB Output is correct
3 Correct 194 ms 110872 KB Output is correct
4 Runtime error 240 ms 131072 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 292 ms 76492 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 334 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -