oj.uz

답안 #585572

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585572 2022-06-29T05:31:00 Z tranxuanbach Islands (IOI08_islands) C++17
70 / 100
 607 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){
            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))]);
                }
            }

            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:                                           |
--------------------------------------------------|

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

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 27732 KB Output is correct
2 Correct 16 ms 27800 KB Output is correct
3 Correct 14 ms 27896 KB Output is correct
4 Correct 14 ms 27732 KB Output is correct
5 Correct 14 ms 27732 KB Output is correct
6 Correct 14 ms 27784 KB Output is correct
7 Correct 14 ms 27700 KB Output is correct
8 Correct 14 ms 27732 KB Output is correct
9 Correct 14 ms 27712 KB Output is correct
10 Correct 14 ms 27732 KB Output is correct
11 Correct 14 ms 27732 KB Output is correct

Subtask #2
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 27860 KB Output is correct
2 Correct 15 ms 27908 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 27860 KB Output is correct
2 Correct 19 ms 28224 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 28976 KB Output is correct
2 Correct 31 ms 32092 KB Output is correct
3 Correct 24 ms 29048 KB Output is correct
4 Correct 22 ms 28428 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 33772 KB Output is correct
2 Correct 46 ms 36168 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 42216 KB Output is correct
2 Correct 89 ms 51556 KB Output is correct
3 Correct 113 ms 68820 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 52192 KB Output is correct
2 Correct 187 ms 92868 KB Output is correct
3 Correct 213 ms 105448 KB Output is correct
4 Runtime error 266 ms 131072 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 291 ms 74764 KB Output is correct
2 Runtime error 607 ms 131072 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 346 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -