Submission #755202

#	Time	Username	Problem	Language	Result	Execution time	Memory
755202		mingli	Islands (IOI08_islands)	C++17	18 / 100	695 ms	131072 KiB

islands

#include "bits/stdc++.h"

#define ll long long
#define all(x) x.begin(), x.end()
#define read(x) for(auto &i : x) cin >> i;
#define sz(x) (int) (x).size()
#define len(x) (int) (x).length()
#define arr array

constexpr int INF = 1e9 + 9;
constexpr long long INF_LL = 1e18 + 9;
constexpr int MOD = 1e9 + 7; // 998244353;

// up, right, down, left
constexpr int mX_4 [] = {0, 1, 0, -1};
constexpr int mY_4 [] = {-1, 0, 1, 0};

using namespace std;

short rand_num(short l, short r) {
    static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
    return uniform_int_distribution<short>(l, r)(gen);
}

template <typename T>
std::ostream& operator<<(std::ostream& _os, const std::pair<T, T>& _p) {
    _os << _p.first << ' ' << _p.second;
    return _os;
}

template <typename T>
void dbg_vec(string str, vector <T> &x) {
    cerr << "DBG " << str << '\n';
    for (int i = 0; i < sz(x); ++i) {
        cerr << "I " << i << " -> " << x[i] << '\n';
    }
    cerr << '\n';
}

const int MAX_BIT_DBG = 3;
void dbg_bits(int n) {
    bitset <MAX_BIT_DBG> v (n);
    cerr << v << '\n';
}

template <typename T>
bool vmin(T &a, T b) { return (a > b ? a = b, true : false); }
 
template <typename T>
bool vmax(T &a, T b) { return (a < b ? a = b, true : false); }

void solve() {
    int n; cin >> n;
    vector <vector <pair <int, int> > > g (n);
    vector <bool> vis (n);
    for (int i = 0; i < n; ++i) {
        int v, w; cin >> v >> w; --v;
        g[i].push_back({v, w});
        g[v].push_back({i, w});
    }

    for (int i = 0; i < n; ++i) {
        sort(all(g[i]), [&] (auto &a, auto &b) {
            return a.second > b.second; 
        });
    }


    vector <vector <pair <int, ll> > > tree (n);

    // creo il dfs tree
    function <void(int, int)> dfs = [&] (int node, int parent) {
        vis[node] = 1;
        for (auto [to, w] : g[node]) {
            if (to == parent or vis[to]) continue;
            tree[node].push_back({to, w});
            dfs(to, node);
        }
    };

    vector <vector <ll> > dp (2, vector <ll> (n));

    function <ll(int, int)> f = [&] (int node, int type) {
        if (dp[type][node]) return dp[type][node];

        // massimi sub problems
        ll mx1 = 0; // massimo 1
        ll mx2 = 0; // massimo 2
        ll sub = 0;
        for (auto [to, w] : tree[node]) {
            // posso decidere di non percorrere l'arco solo se non mi sono collegato a nessuno
            if (type == 0) {
                sub = f(to, type);
            }

            // percorro l'arco 
            vmax(sub, f(to, 1) + w);

            if (sub > mx1) {
                mx2 = mx1;
                mx1 = sub;
            } else if (sub > mx2) {
                mx2 = sub;
            }
        }

        return dp[type][node] = (mx1 + (type ?  0 : mx2));
    };

    ll ans = 0;
    for (int node = 0; node < n; ++node) {
        if (!vis[node]) {
            dfs(node, node);
            // cerr << "Node " << node << '\n';
            ans += f(node, 0);
        }
    }

    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tt = 1; // cin >> tt;
    while (tt--) solve();
    return 0;
}

• Subtask 1: 18 / 33
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10