oj.uz

Submission #407242

# Submission time Handle Problem Language Result Execution time Memory
407242 2021-05-18T16:29:07 Z Aldas25 Islands (IOI08_islands) C++14
60 / 100
 2000 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;
        }

        FOR(a, 0, len-1) FOR(b, a+1, len-1) {
            ll cr = dp[cycle[a]][0] + dp[cycle[b]][0];
            cr += max(pref[b] - pref[a], cycleWalkLen-pref[b]+pref[a]);
            curMax = max(curMax, cr);
            //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

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23804 KB Output is correct
2 Correct 14 ms 23848 KB Output is correct
3 Correct 14 ms 23860 KB Output is correct
4 Correct 14 ms 23776 KB Output is correct
5 Correct 13 ms 23776 KB Output is correct
6 Correct 14 ms 23756 KB Output is correct
7 Correct 14 ms 23756 KB Output is correct
8 Correct 14 ms 23836 KB Output is correct
9 Correct 14 ms 23824 KB Output is correct
10 Correct 14 ms 23756 KB Output is correct
11 Correct 14 ms 23820 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23904 KB Output is correct
2 Correct 14 ms 23948 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23960 KB Output is correct
2 Correct 21 ms 24396 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 25320 KB Output is correct
2 Correct 438 ms 28628 KB Output is correct
3 Correct 24 ms 25628 KB Output is correct
4 Correct 19 ms 24764 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 660 ms 30544 KB Output is correct
2 Correct 764 ms 33880 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 43392 KB Output is correct
2 Execution timed out 2078 ms 45684 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1862 ms 58668 KB Output is correct
2 Execution timed out 2075 ms 89036 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 98968 KB Output is correct
2 Runtime error 519 ms 131076 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 376 ms 131076 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -