Submission #1302401

#TimeUsernameProblemLanguageResultExecution timeMemory
1302401red_soulsCities (BOI16_cities)C++20
0 / 100
80 ms25752 KiB
#include <bits/stdc++.h>
#define ll long long
#define task "cities"
using namespace std;

const int N = 2e5 + 16;
int n, K, m, u, v;
ll w;
vector <int> critical;

struct edge {
    int u, v;
    ll w;

    bool operator < (const edge &other) const {
        return w < other.w;
    }
};

edge edgeList[N];

/*
4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8
*/

/*
10 3 12

1 5 10

1 2 4
1 3 10
3 4 8
2 4 5
4 5 6
3 5 7
3 6 9
6 7 2
6 8 3
7 9 16
8 9 16
9 10 20
*/

namespace sub5 {

    struct dsu {
        int parent[N], sz[N];

        void makeSet(int k) {
            parent[k] = k;
            sz[k] = 1;
        }

        int findSet(int k) {
            if (k == parent[k]) {
                return k;
            }
            int p = findSet(parent[k]);
            parent[k] = p;
            return p;
        }

        bool unionSet(int a, int b) {
            a = findSet(a);
            b = findSet(b);
            if (a != b) {
                if (sz[a] < sz[b]) {
                    swap(a, b);
                }
                parent[b] = a;
                sz[a] += sz[b];
                return true;
            }
            return false;
        }
    };

    dsu g1;

    vector <edge> need;
    ll mst;

    vector <int> adj[N];
    int cnt, st[N], sparse[26][N << 2], h[N], f[N];

    void dfs(int k, int p) {
        sparse[0][++cnt] = k;
        st[k] = cnt;
        for (auto v : adj[k]) {
            if (v == p) {
                continue;
            }
            h[v] = h[k] + 1;
            dfs(v, k);
            sparse[0][++cnt] = k;
        }
    }

    int lca(int u, int v) {
        int l = st[u], r = st[v];
        if (l > r) {
            swap(l, r);
        }
        int k = __lg(r - l + 1);
        if (h[sparse[k][l]] < h[sparse[k][r - (1 << k) + 1]]) {
            return sparse[k][l];
        }
        return sparse[k][r - (1 << k) + 1];
    }

    void dpCalc(int k, int p) {
        for (auto v : adj[k]) {
            if (v == p) {
                continue;
            }
            dpCalc(v, k);
            f[k] += f[v];
        }
    }

    void solve() {
        sort(edgeList + 1, edgeList + 1 + m);
        for (int i = 1; i <= n; i++) {
            g1.makeSet(i);
        }
        for (int i = 1; i <= m; i++) {
            u = edgeList[i].u;
            v = edgeList[i].v;
            w = edgeList[i].w;
            if (g1.unionSet(u, v)) {
                need.push_back({u, v, w});
                mst += w;
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
        }
        dfs(1, 1);
        for (int j = 1; j <= 20; j++) {
            for (int i = 1; i + (1 << j) - 1 <= cnt; i++) {
                if (h[sparse[j - 1][i]] < h[sparse[j - 1][i + (1 << (j - 1))]]) {
                    sparse[j][i] = sparse[j - 1][i];
                }
                else {
                    sparse[j][i] = sparse[j - 1][i + (1 << (j - 1))];
                }
            }
        }
        for (auto &x : need) {
            if (h[x.u] > h[x.v]) {
                swap(x.u, x.v);
            }
        }
        for (int i = 0; i < critical.size(); i++) {
            for (int j = i + 1; j < critical.size(); j++) {
                u = critical[i];
                v = critical[j];
                f[u]++;
                f[v]++;
                f[lca(u, v)] -= 2;
            }
        }
        dpCalc(1, 1);
        for (auto x : need) {
            if (f[x.v] == 0) {
                mst -= x.w;
            }
        }
        cout << mst;
    }
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    cin >> n >> K >> m;
    for (int i = 1; i <= K; i++) {
        cin >> u;
        critical.push_back(u);
    }
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        edgeList[i] = {u, v, w};
    }
    sub5 :: solve();

    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:187:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  187 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...