oj.uz

답안 #585549

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585549 2022-06-29T04:56:46 Z tranxuanbach Islands (IOI08_islands) C++17
0 / 100
 352 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;
            }
            
            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;
                }
                if (j > i){
                    tans = max(tans, chain[node[i]] + dist + prefdist[i] + query(j, len - 1, mxc));
                    tans = max(tans, chain[node[i]] + prefdist[i] + query(0, i - 1, mxc));
                }
                else{
                    tans = max(tans, chain[node[i]] + prefdist[i] + query(j, i - 1, mxc));
                }
                hdist -= b[node[i]];
            }
            ans += tans;
        }
    }

    cout << ans << endl;
}

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

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

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

Subtask #1
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 27732 KB Output isn't correct
2 Incorrect 14 ms 27732 KB Output isn't correct
3 Incorrect 14 ms 27860 KB Output isn't correct
4 Incorrect 14 ms 27732 KB Output isn't correct
5 Incorrect 14 ms 27720 KB Output isn't correct
6 Incorrect 13 ms 27740 KB Output isn't correct
7 Incorrect 13 ms 27732 KB Output isn't correct
8 Incorrect 13 ms 27748 KB Output isn't correct
9 Incorrect 13 ms 27732 KB Output isn't correct
10 Incorrect 13 ms 27732 KB Output isn't correct
11 Incorrect 15 ms 27784 KB Output isn't correct

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 27860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 27932 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 29192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 34488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 92 ms 44664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 141 ms 57560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 323 ms 90280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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