oj.uz

답안 #407251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
407251 2021-05-18T16:34:11 Z Aldas25 Islands (IOI08_islands) C++14
80 / 100
 519 ms 131076 KB 
#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;
        }

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

        ans += curMax;
    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 14 ms 23756 KB Output is correct
3 Correct 13 ms 23884 KB Output is correct
4 Correct 13 ms 23768 KB Output is correct
5 Correct 13 ms 23852 KB Output is correct
6 Correct 14 ms 23756 KB Output is correct
7 Correct 14 ms 23784 KB Output is correct
8 Correct 14 ms 23756 KB Output is correct
9 Correct 14 ms 23756 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 14 ms 23756 KB Output is correct

Subtask #2
3.0 / 3.0

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

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23884 KB Output is correct
2 Correct 16 ms 24280 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 25164 KB Output is correct
2 Correct 31 ms 28144 KB Output is correct
3 Correct 24 ms 25428 KB Output is correct
4 Correct 19 ms 24568 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 29812 KB Output is correct
2 Correct 50 ms 32660 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 40900 KB Output is correct
2 Correct 109 ms 45700 KB Output is correct
3 Correct 126 ms 62764 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 53272 KB Output is correct
2 Correct 217 ms 83376 KB Output is correct
3 Correct 233 ms 91196 KB Output is correct
4 Correct 286 ms 123488 KB Output is correct

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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