oj.uz

Submission #791827

# Submission time Handle Problem Language Result Execution time Memory
791827 2023-07-24T10:39:03 Z phoebe Islands (IOI08_islands) C++17
100 / 100
 712 ms 106720 KB 
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define ll long long
#define pii pair<ll, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;

const int maxn = 1e6 + 10;
int n, p[maxn], l[maxn], idx[maxn] = {0}; // 0 = unseen, 1 = seeing, 2 = seen
ll val[maxn], cur = 0, re = 0; 
// bool on_cycle[maxn] = {0};
bitset<maxn> on_cycle, seen, cur_seen;
vector<int> adj[maxn];
stack<pii> s;

// void dfs(int v, int p){
//     val[v] = 0;
//     ll best = -1, second_best = -1;
//     for (auto u : adj[v]){
//         if (on_cycle[u] || u == p) continue;
//         dfs(u, v);
//         val[v] = max(val[v], val[u] + l[u]);
//         if (best == -1) best = val[u] + l[u];
//         else second_best = max(second_best, val[u] + l[u]);
//         if (second_best > best) swap(best, second_best);
//     }
//     cur = max(cur, best + second_best);
// }

void dfs(int v, int p){
    s.push({v, p});
    while (!s.empty()){
        int v = s.top().F, p = s.top().S; 
        bool seen_all_children = true;
        while (idx[v] < adj[v].size()){
            int u = adj[v][idx[v]++];
            if (on_cycle[u] || u == p) continue;
            seen_all_children = false;
            s.push({u, v}); break;
        }
        if (!seen_all_children) continue;
        val[v] = 0;
        ll best = -1, second_best = -1;
        for (auto u : adj[v]){
            if (on_cycle[u] || u == p) continue;
            val[v] = max(val[v], val[u] + l[u]);
            if (best == -1) best = val[u] + l[u];
            else second_best = max(second_best, val[u] + l[u]);
            if (second_best > best) swap(best, second_best);
        }
        cur = max(cur, best + second_best);
        s.pop();
    }
}

void solve(int s, int sz, ll total_sum){
    int v = s;
    ll cw = -LLINF, ccw = -LLINF, cur_sum = 0;
    FOR(i, sz){
        cur = max(cur, cw + val[v] + cur_sum);
        cur = max(cur, ccw + val[v] + (total_sum - cur_sum));
        cw = max(cw, val[v] - cur_sum);
        ccw = max(ccw, val[v] + cur_sum);
        cur_sum += l[v]; v = p[v];
    }
}

void find_cycle(int s){
    int v = s; 
    while (!cur_seen[v]){ // while unseen
        cur_seen[v] = true; v = p[v];
    }
    if (cur_seen[v] && !seen[v]){ // found a cycle
        cur = 0; int sz = 0; ll total_sum = 0;
        while (!on_cycle[v]){
            total_sum += l[v];
            sz++; on_cycle[v] = true; v = p[v];
        }
        FOR(i, sz){
            dfs(v, v); v = p[v];
        }
        solve(v, sz, total_sum);
        re += cur;
    }
    v = s; 
    while (!seen[v]){
        seen[v] = true; v = p[v];
    }
}

signed main(){
    NYOOM;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> p[i] >> l[i];
        adj[p[i]].PB(i);
    }
    for (int i = 1; i <= n; i++){
        if (seen[i] != 2) find_cycle(i);
    }
    cout << re;
}

Compilation message

islands.cpp: In function 'void dfs(int, int)':
islands.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         while (idx[v] < adj[v].size()){
      |                ~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23836 KB Output is correct
2 Correct 14 ms 23816 KB Output is correct
3 Correct 13 ms 23868 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23820 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23812 KB Output is correct
8 Correct 13 ms 23764 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 13 ms 23812 KB Output is correct
11 Correct 12 ms 23764 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23892 KB Output is correct
2 Correct 12 ms 23856 KB Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24644 KB Output is correct
2 Correct 22 ms 25424 KB Output is correct
3 Correct 19 ms 24888 KB Output is correct
4 Correct 15 ms 24300 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 26248 KB Output is correct
2 Correct 32 ms 29036 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 32704 KB Output is correct
2 Correct 67 ms 36672 KB Output is correct
3 Correct 80 ms 35024 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 41892 KB Output is correct
2 Correct 120 ms 43208 KB Output is correct
3 Correct 137 ms 55704 KB Output is correct
4 Correct 156 ms 50236 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 45280 KB Output is correct
2 Correct 437 ms 59288 KB Output is correct
3 Correct 182 ms 56056 KB Output is correct
4 Correct 236 ms 63108 KB Output is correct
5 Correct 223 ms 60860 KB Output is correct
6 Correct 712 ms 63788 KB Output is correct
7 Correct 238 ms 63624 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 106720 KB Output is correct
2 Correct 229 ms 98708 KB Output is correct
3 Correct 272 ms 90480 KB Output is correct
4 Correct 227 ms 89896 KB Output is correct
5 Correct 219 ms 73668 KB Output is correct
6 Correct 217 ms 77648 KB Output is correct
7 Correct 672 ms 77760 KB Output is correct