Submission #517335

#	Time	Username	Problem	Language	Result	Execution time	Memory
517335		tzuyuna	Cities (BOI16_cities)	C++17	0 / 100	6054 ms	51548 KiB

cities

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

struct edge {
    int u, v, c;
};

int N, K, M, ans;
vector<pi> adj[100010], new_adj[100010];
vector<edge> edgelist, tree;
vector<int> big;
set<int> nodes;
int par[100010];
int twok[100010][20], depth[100010], dist[100010];

struct DSU {
    void init() {for (int i = 0; i <= N; ++i) par[i] = i;}
    int root(int x) { return (par[x]==x)? x:par[x]=root(par[x]); }
    bool same(int a, int b) { return root(a) == root(b); }
    void merge(int a, int b) {
        par[root(a)] = root(b);
    }
};

struct TWOK {
    void init() {memset(twok, -1, sizeof twok);}
    void dfs(int x, int p, int d, int wd) {
        depth[x] = d;
        dist[x] = wd;
        twok[x][0] = p;
        for (int i = 1; i <= 17; i++) {
            if (twok[x][i - 1] == -1) break;
            twok[x][i] = twok[twok[x][i - 1]][i - 1];
        }
        for (auto it: new_adj[x]) {
            if (it.fi != p) dfs(it.fi,x,d+1,wd+it.si);
        }
    }
    int kth_parent(int x, int k) {
        for (int i = 0; i <= 17; i++) {
            if (x == -1) return -1;
            if (k & (1 << i)) x = twok[x][i];
        }
        return x;
    }
    int lca(int x, int y) {
        if (depth[x] > depth[y]) {
            int dd = depth[x] - depth[y];
            x = kth_parent(x, dd);
        } else {
            int dd = depth[y] - depth[x];
            y = kth_parent(y, dd);
        }
        if (x == y) return x;
        for (int i = 17; i >= 0; i--) {
            if (twok[x][i] != twok[y][i]) {
                x = twok[x][i];
                y = twok[y][i];
            }
        }
        return twok[x][0];
    }   
    int getdist(int x, int y) {
        return dist[x] + dist[y] - 2 * dist[lca(x, y)];
    }
};

signed main() {
    fast;
    cin >> N >> K >> M;
    for (int i = 1; i <= K; ++i) {
        int x; cin >> x;
        big.pb(x);
    }
    for (int i = 1; i <= M; ++i) {
        int u, v, c; cin >> u >> v >> c;
        adj[u].pb({v, c});
        adj[v].pb({u, c});
        edgelist.pb({u, v, c});
    }   
    sort(edgelist.begin(), edgelist.end(), [](edge a, edge b) {
        return a.c < b.c;
    });
    DSU dsu;
    dsu.init();
    for (auto i: edgelist) {
        if (dsu.same(i.u, i.v)) continue;
        dsu.merge(i.u, i.v);
        new_adj[i.u].pb({i.v, i.c});
        new_adj[i.v].pb({i.u, i.c});
        nodes.insert(i.u);
        nodes.insert(i.v);
    }
    TWOK decomp;
    decomp.init();
    decomp.dfs(*nodes.begin(), -1, 0, 0);
    set<int> marked;
    for (auto i: nodes) {
        for (auto j: nodes) {
            if (i == j) continue;
            marked.insert(decomp.lca(i, j));
        }
    }
    for (auto i: nodes) marked.insert(i);
    for (auto i: marked) {
        for (auto j: marked) {
            if (i == j) continue;
            tree.pb({i, j, decomp.getdist(i, j)});
        }
    }
    sort(tree.begin(), tree.end(), [](edge a, edge b) {
        return a.c < b.c;
    });
    dsu.init();
    for (auto i: tree) {
        // debug(i.u, i.v, i.c);
        if (dsu.same(i.u, i.v)) {
            // debug(i.u, i.v);
            continue;
        }
        dsu.merge(i.u, i.v);
        ans += i.c;
    }
    cout << ans; 
    return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26