Submission #432567

#	Time	Username	Problem	Language	Result	Execution time	Memory
432567		tengiz05	Islands (IOI08_islands)	C++17	0 / 100	2094 ms	131076 KiB

islands

#include <bits/stdc++.h>
using i64 = long long;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<std::set<std::pair<int, int>>> e(n), al(n);
    for (int i = 0; i < n; i++) {
        int to, cost;
        std::cin >> to >> cost;
        to--;
        e[i].emplace(to, cost);
        e[to].emplace(i, cost);
        al[i].emplace(to, cost);
        al[to].emplace(i, cost);
    }
    std::vector<bool> vis(n);
    int timer = 0;
    std::vector<int> in(n), low(n);
    std::vector<std::tuple<int, int, int>> br;
    std::function<void(int, int)> dfs = [&](int u, int p) {
        in[u] = low[u] = timer++;
        vis[u] = true;
        for (auto [v, w] : e[u]) {
            if (v == p) {
                continue;
            }
            if (vis[v]) {
                low[u] = std::min(low[u], in[v]);
            } else {
                dfs(v, u);
                low[u] = std::min(low[u], low[v]);
                if (low[v] > in[u]) {
                    // bridge u -> v
                    br.emplace_back(u, v, w);
                }
            }
        }
    };
    for (int i = 0; i < n; i++) {
        if (!vis[i]) 
            dfs(0, -1);
    }
    for (auto [x, y, z] : br) {
        al[x].erase(al[x].lower_bound({y, z}));
        al[y].erase(al[y].lower_bound({x, z}));
    }
    std::vector<i64> v{0}, pos(n, 0), comp(n), sum(n);
    std::iota(pos.begin(), pos.end(), 0);
    std::vector<std::vector<int>> contain;
    vis.assign(n, false);    timer = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i]) {
            continue;
        }
        comp[i] = timer;
        pos[i] = v.size();
        v.push_back(v.back());
        contain.push_back({});
        if (al[i].size()) {
            int u = i;
            contain[timer].push_back(u);
            vis[u] = true;
            while (!vis[al[u].begin()->first] || !vis[(++al[u].begin())->first]) {
                i64 cost;
                if (vis[al[u].begin()->first]) {
                    u = (++al[u].begin())->first;
                    cost = (++al[u].begin())->second;
                } else {
                    u = al[u].begin()->first;
                    cost = al[u].begin()->second;
                }
                contain[timer].push_back(u);
                vis[u] = true;
                comp[u] = timer;
                pos[u] = v.size();
                sum[timer] += cost;
                v.push_back(v.back() + cost);
            }
                if (vis[al[u].begin()->first]) {
                    sum[timer] += (++al[u].begin())->second;
                } else {
                    sum[timer] += al[u].begin()->second;
                }
        }
        timer++;
    }
    // std::cerr << "what the fuck\n";
    // for (int i = 0; i < n; i++) {
    //     std::cout << comp[i] << " \n"[i == n - 1];
    // }
    for (int i = 0; i < n; i++) {
        e[i].clear();
    }
    for (auto [x, y, z] : br) {
        e[x].insert({y, z});
        e[y].insert({x, z});
    }
    i64 ans = 0;
    std::vector<i64> f(n);
    for (int i = 0; i < timer; i++) {
        i64 res = 0;
        std::function<i64(int, int)> dfs2 = [&](int u, int p) -> i64 {
            i64 mx = 0;
            for (auto [v, w] : e[u]) {
                if (v != p) {
                    mx = std::max(mx, dfs2(v, u) + w);
                }
            }
            return mx;
        };
        for (auto u : contain[i]) {
            f[u] = dfs2(u, -1);
        }
        for (auto U : contain[i]) {
            for (auto V : contain[i]) {
                if (U == V) continue;
                assert(comp[U] == comp[V]);
                if (pos[U] > pos[V]) std::swap(U, V);
                if (U == 1 && V == 6) {
                    // std::cout << "YES ";
                    // std::cout << sum[comp[U]] << " " << v[pos[V]] - v[pos[U] - 1] << "\n";
                }
                res = std::max(res, f[U] + f[V] + std::max(v[pos[V]] - v[pos[U] - 1], sum[comp[U]] - (v[pos[V]] - v[pos[U] - 1])));
            }
        }
        ans += res;
        // std::cout << ans << "\n";
    }
    // for (int i = 0; i < n; i++) {
    //     std::cout << f[i] << " \n"[i == n - 1];
    // }
    std::cout << ans << "\n";
    return 0;
}



















/*




    auto dij = [&](int s) {
        std::priority_queue<std::pair<int, int>> q;
        q.emplace(0, s);
        std::vector<int> dist(n, -1e9);
        dist[s] = 0;
        while (!q.empty()) {
            auto [d, u] = q.top();
            if (s == 0) {
                std::cout << u << "\n";
            }
            q.pop();
            for (auto [v, w] : e[u]) {
                if (dist[v] < dist[u] + w) {
                    q.emplace(dist[v], v);
                }
            }
        }
        std::pair<int, int> mx = {0, s};
        for (int i = 0; i < n; i++) {
            mx = std::max(mx, {dist[i], i});
            if (s == 0) {
                std::cout << dist[i] << " ";
            }
        }
        return mx;
    };
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0 || true) {
            auto [dist, u] = dij(i);
            ans = std::max(ans, dist);
        }
    }*/

• Subtask 1: 0 / 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