Submission #942002

# Submission time Handle Problem Language Result Execution time Memory
942002 2024-03-10T01:53:08 Z riariti Toll (APIO13_toll) C++17
100 / 100
2434 ms 13512 KB
#line 1 "Toll.cpp"
#include <bits/stdc++.h>

#line 2 "/Users/jeff/Documents/git_repos/competitive/cplib/environment/dbg.hpp"

#if defined(local)
#include <debug>
#else
#define dbg(...)
#endif
#line 4 "Toll.cpp"

struct DSU {
    int n;
    std::vector<int> f;
    std::vector<int> siz;

    DSU() {}
    explicit DSU(int _n) : n(_n), f(_n), siz(_n) {
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, -1);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }

        return x;
    }

    bool same(int x, int y) { return find(x) == find(y); }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) {
            return false;
        }

        siz[x] += siz[y];
        f[y] = x;

        return true;
    }

    int size(int x) { return siz[find(x)]; }
};

std::int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

#define int std::int64_t

    // https://dmoj.ca/problem/apio13p2/editorial
    // getting used to style :()
    // got until observation 3 without any doubts

    // // kruskal-ish way
    // std::sort(abc.begin(), abc.end(),
    //           [&](auto x, auto y) { return x[2] < y[2]; });

    // // K <= 20 => 2^K = 1048576
    // // bitmasks which of them we should take then put max value so that they
    // are
    // // still included in minimum spanning tree

    // const auto k = 1 << K;

    // // store the max weight so that edge is contained only compared to the
    // // other constant it possibly does not change what about cases where it
    // is
    // // compared to other non-constants
    //    // kruskal on original edges
    // connect 2 components (see if there were additional edges)
    // atrribute that you can replace the edge with the additional edges (now
    // are a group of edges)
    // choose any 1 from the group
    // weight = to original weight
    // nah

    constexpr int INF = 1E9 + 9;

    int N, M, K;
    std::cin >> N >> M >> K;
    dbg(N, M, K);
    std::vector<std::array<int, 3>> abc(M);
    for (int i = 0; i < M; i++) {
        auto &[a, b, c] = abc[i];
        std::cin >> a >> b >> c;
        // a--;
        // b--;
    }
    std::vector<std::array<int, 3>> xy(K);
    for (int i = 0; i < K; i++) {
        auto &[x, y, w] = xy[i];
        std::cin >> x >> y;
        // w = INF;
        // x--;
        // y--;
    }
    std::vector<int> c(N);
    for (int i = 0; i < N; i++) {
        std::cin >> c[i];
    }

    // sol(N, M, K, abc, xy, c);

    for (int i = 0; i < M; i++) {
        auto &[a, b, c] = abc[i];
        a--;
        b--;
    }
    for (int i = 0; i < K; i++) {
        auto &[x, y, w] = xy[i];

        w = INF;
        x--;
        y--;
    }
    dbg(abc);
    dbg(xy);
    dbg(c);

    std::vector<std::array<int, 3>> mst;
    auto kruskal = [&]() -> void {
        // make mst
        std::sort(abc.begin(), abc.end(),
                  [](const auto &x, const auto &y) { return x[2] < y[2]; });
        dbg(abc);

        // kruskal
        DSU dsu(N);
        for (int i = 0; i < M; i++) {
            auto [a, b, c] = abc[i];

            if (dsu.merge(a, b)) {
                mst.push_back({a, b, c});
            }
        }
        dbg(mst);
    };
    kruskal();

    // dont need the bad ori edges / extra useless weight
    abc = std::move(mst);
    mst.clear();

    dbg(abc);

    // M = N - 1
    M = abc.size();
    dbg(M);

    // compress into at max k components (since that is what the questin says)
    // => local (inside) and global path for each component
    // local does not change, at max k vertexs, one from each from current to
    // outside component (at max k components)
    // value is from root until the local root (root of the compoent ) is called
    // global path else inside it is called local path (computation to all can
    // be done via O(n) + O(1) of lca or O(nk) with simple dfs or O(n) with dfs
    // + rerooting)
    // local cost does not depend on query but global does => lcoal cost precomp
    // + global cost recalc with dfs O(k) vertexs only can be done in O(nk + 2^k
    // * k) or O(n + 2^k * k) both passable

    std::vector<std::vector<int>> adj(N);
    // components mapping, number of people
    std::vector<int> cmp(N, -1), np(N);
    int C = -1;
    // not part of k vertexs
    std::vector<std::array<int, 3>> npk;
    // compression to differniate the k edges and original edges and then group
    // them up into components for quicker query since local does not change
    // only global does, and so we have to compress as mentioned above
    auto compress = [&]() -> void {
        DSU dsu(N);

        // choose the vertexs which get affected by the k new nodes
        // / the k edges themselves
        for (int i = 0; i < K; i++) {
            auto [x, y, w] = xy[i];
            dbg(x, y, w);

            if (dsu.merge(x, y)) {
                dbg(x, y);
            }
        }

        // go through the mst to see which paths between vertexs get affected
        for (int i = 0; i < M; i++) {
            auto [a, b, c] = abc[i];

            if (dsu.merge(a, b)) {
                dbg(a, b);
                // ok so not affected => take
                // dont put the graph edge of x y
                // since we want to find the compoents where it is seperated
                adj[a].push_back(b);
                adj[b].push_back(a);
            } else {
                // affeceted => cant take => but still compress
                // to see where the nodes end up at i.e which component
                // part of the components centered by the above k vertexs

                // will be used especially since we are not going to take all of
                // the K all the K edges, sometimes only a subset
                npk.push_back({a, b, c});
            }
        }
        dbg(npk);

        // fill in components i.e what component will vertex a, b and so on
        // belong to and how many people are from there
        dbg(cmp);
        for (int i = 0, p = 0; i < N; i++) {
            if (cmp[i] != -1) {
                continue;
            }

            auto dfs = [&](auto &&self, int x) {
                // baiscally like vis
                if (cmp[x] != -1) {
                    return;
                }

                dbg(np[p], c[x]);
                np[p] += c[x];
                cmp[x] = p;

                for (auto y : adj[x]) {
                    self(self, y);
                }
            };
            dfs(dfs, i);

            p++;
            C = p;
        }
        dbg(cmp, C);
        dbg(np);

        // convert them to components
        for (int i = 0; i < npk.size(); i++) {
            auto &[a, b, c] = npk[i];

            a = cmp[a];
            b = cmp[b];

            dbg(a, b);
        }

        // convert the k edges into which compoentes they belng to
        for (int i = 0; i < K; i++) {
            auto &[x, y, w] = xy[i];

            x = cmp[x];
            y = cmp[y];

            dbg(x, y);
        }
    };
    compress();

    auto sol = [&](const std::vector<int> &idx) -> std::int64_t {
        dbg(idx);

        DSU dsu(C);
        std::vector<std::vector<std::pair<int, int>>> gdj(C);

        for (auto i : idx) {
            auto [x, y, w] = xy[i];

            // it should not be a cycle
            if (!dsu.merge(x, y)) {
                return -1;
            }

            dbg(x, y);

            // 1 weight and 0 for the non (chosen) k edges and original edges
            // for check function since we only can add values if they pass
            // through this edge
            gdj[x].push_back({y, 1});
            gdj[y].push_back({x, 1});
        }
        // dbg(gdj);

        // again similar with compression, but now only with the non chosen k
        // edges
        std::vector<std::array<int, 3>> npl;
        // make sure onyl from the original non (all) k edges
        for (auto [a, b, c] : npk) {
            dbg(a, b, c);

            if (dsu.merge(a, b)) {
                dbg("here", a, b);
                // 0 for the non profit edges
                gdj[a].push_back({b, 0});
                gdj[b].push_back({a, 0});
            } else {
                npl.push_back({a, b, c});
            }
        }
        dbg(npl);

        std::vector<int> par(C, -1), chk(C), dep(C), siz(C);
        // np = weight of edges that will get paid from
        // pae = all k's edges or nah (will be used for cost calc or nah)
        std::vector<int> pae(C);
        // std::vector<int> np(N), pae(N);
        // np alreadyinitialized
        // O(K) vertexs
        auto dfs = [&](auto &&self, int x) -> void {
            // siz is number fo people
            siz[x] = np[x];
            for (auto [y, w] : gdj[x]) {
                if (y == par[x]) {
                    continue;
                }

                par[y] = x;
                chk[y] = w;
                dep[y] = dep[x] + 1;
                pae[y] = INF;

                self(self, y);

                siz[x] += siz[y];
            }
        };
        dfs(dfs, 0);

        dbg(par);
        dbg(chk);
        dbg(dep);
        dbg(siz);
        dbg(np);
        dbg(pae);

        for (auto [a, b, c] : npl) {
            // mins here are to check if all of them are have weight
            // the min weight here is the dependent on the k edges
            // so the win weight / cost of the k edges here are the 0's and 1's
            // basically checking if it will benefit him or nah

            // if it passess through only the k edgees then only will the val
            // will be 1 else 0 i.e the person wont get any money
            // and it si possible since siz is basicaly like a prefix sum
            // so if we add it onyl where it passes through the kedges => it is
            // still answer since it tells how many people pass through it
            // confirm

            // lca path checking basically
            if (dep[a] < dep[b]) {
                std::swap(a, b);
            }

            // equalize depth
            while (dep[a] > dep[b]) {
                pae[a] = std::min(pae[a], c);
                a = par[a];
            }

            // lca
            while (a != b) {
                pae[a] = std::min(pae[a], c);
                pae[b] = std::min(pae[b], c);

                a = par[a];
                b = par[b];
            }
        }

        int ans = 0;
        for (int i = 1; i < C; i++) {
            if (!chk[i]) {
                continue;
            }

            ans += siz[i] * pae[i];
        }

        return ans;
    };

    const auto bit_set = [](int v, int k) -> bool { return v & (1 << k); };

    std::int64_t ans = 0;
    for (int k = 0; k < (1 << K); k++) {
        std::vector<int> idx;
        for (int i = 0; i < K; i++) {
            if (!bit_set(k, i)) {
                continue;
            }

            idx.push_back(i);
        }

        ans = std::max(ans, sol(idx));
    }

    std::cout << ans << "\n";

#undef int

    return 0;
}

Compilation message

Toll.cpp: In lambda function:
Toll.cpp:238:27: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::array<long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 160 ms 12980 KB Output is correct
8 Correct 174 ms 12232 KB Output is correct
9 Correct 168 ms 12208 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 160 ms 12980 KB Output is correct
8 Correct 174 ms 12232 KB Output is correct
9 Correct 168 ms 12208 KB Output is correct
10 Correct 1841 ms 12236 KB Output is correct
11 Correct 2419 ms 12236 KB Output is correct
12 Correct 2434 ms 13512 KB Output is correct