Submission #661308

#	Time	Username	Problem	Language	Result	Execution time	Memory
661308		zse	Logistical Metropolis (KRIII5_LM)	C++17	0 / 7	18 ms	20948 KiB

LM

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define vpii vector<pii>
#define vi vector<int>

int N, M;

int cnt = 0;
int anc[100000][17];
int depth[100000];
int mx[100000][17];
int in[100000];
int out[100000];

vpii adj[100000];
vpii mst[100000];
struct Edge { int u, v, d; } E[300000];

int dsu[100000];

int find(int a) { return dsu[a] = a == dsu[a] ? a : find(dsu[a]); }
void merge(int a, int b) { a = find(a); b = find(b); dsu[a] = b; }

bool cmp1(int i, int j) { return in[i] < in[j]; }
bool cmp2(Edge a, Edge b) { return a.d < b.d; }

void dfs(int n) {
    in[n] = cnt++;
    for (auto [m, d]: mst[n]) {
        if (anc[n][0] == m) continue;
        anc[m][0] = n;
        mx[m][0] = d;
        depth[m] = depth[n] + 1;
        dfs(m);
    }
    out[n] = cnt;
}

void initLCA() {
    for (int i = 1; i < 17; i++) {
        for (int n = 0; n < N; n++) {
            if (anc[n][i-1] == -1) continue;
            anc[n][i] = anc[anc[n][i-1]][i-1];
            mx[n][i] = max(mx[n][i-1], mx[anc[n][i-1]][i-1]);
        }
    }
}

int LCA(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);
    for (int i = 16; i >= 0; i--) {
        if (depth[b]-depth[a] >= (1<<i)) b = anc[b][i];
    }
    if (a == b) return a;
    for (int i = 16; i >= 0; i--) {
        if (anc[a][i] != anc[b][i]) a = anc[a][i], b = anc[b][i];
    }
    return anc[a][0];
}

int getMx(int a, int b) {
    int ret = 0;
    if (depth[a] > depth[b]) swap(a, b);
    for (int i = 16; i >= 0; i--) {
        if (depth[b]-depth[a] >= (1<<i)) {
            ret = max(ret, mx[b][i]);
            b = anc[b][i];
        }
    }
    if (a == b) return ret;
    for (int i = 16; i >= 0; i--) {
        if (anc[a][i] != anc[b][i]) {
            a = anc[a][i], b = anc[b][i];
            ret = max(ret, max(mx[a][i], mx[b][i]));
        }
    }
    ret = max(ret, max(mx[a][0], mx[b][0]));
    return ret;
}

ll kruskal() {
    ll ret = 0;
    sort(E, E+M, cmp2);
    for (int n = 0; n < N; n++) dsu[n] = n;
    for (int m = 0; m < M; m++) {
        auto [u, v, d] = E[m];
        if (find(u) == find(v)) continue;
        merge(u, v);
        ret += d;
        mst[u].push_back({ v, d });
        mst[v].push_back({ u, d });
    }
    return ret;
}

vpii tadj[100000];
bool flag[100000];

bool isanc(int a, int b) { return in[a] < in[b] && in[b] < out[a]; }

ll dp(int n, int s, int p) {
    ll ret = 0;
    for (auto [m, w]: tadj[n]) {
        if (m == p) continue;
        if (s == 0) ret += dp(m, flag[m], n);
        else {
            if (flag[m]) ret += w + dp(m, 1, n);
            else ret += max(w + dp(m, 0, n), dp(m, 1, n));
        }
    }
    return ret;
}

ll solve(int n) {
    vi v = { n }; flag[n] = 1;
    for (auto [m, w]: adj[n]) { v.push_back(m); flag[m] = 1; }
    sort(v.begin(), v.end(), cmp1);
    int tmp = v.size();
    for (int i = 0; i < tmp-1; i++) v.push_back(LCA(v[i], v[i+1]));
    sort(v.begin(), v.end(), cmp1);
    v.erase(unique(v.begin(), v.end()), v.end());

    for (int m: v) tadj[m] = {};
    stack<int> st;
    for (int m: v) {
        while (st.size() && !isanc(st.top(), m)) {
            int a = st.top(); st.pop();
            int d = getMx(a, st.top());
            tadj[st.top()].push_back({ a, d });
            tadj[a].push_back({ st.top(), d });
        }
        st.push(m);
    }
    while (st.size() >= 2) {
        int a = st.top(); st.pop();
        int d = getMx(a, st.top());
        tadj[st.top()].push_back({ a, d });
        tadj[a].push_back({ st.top(), d });
    }
    ll ret = dp(n, 1, -1);
    for (int m: v) flag[m] = 0;
    return ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    memset(anc, -1, sizeof(anc));
    memset(mx, 0, sizeof(mx));
    memset(flag, 0, sizeof(flag));

    cin >> N >> M;
    for (int m = 0; m < M; m++) {
        int u, v, d; cin >> u >> v >> d; u--; v--;
        adj[u].push_back({ v, d });
        adj[v].push_back({ u, d });
        E[m] = { u, v, d };
    }
    ll sum = kruskal();
    anc[0][0] = -1; depth[0] = 0; dfs(0);
    initLCA();

    for (int n = 0; n < N; n++) {
        ll ans = sum;
        for (auto [m, w]: adj[n]) ans += w;
        ans -= solve(n);
        cout << ans << '\n';
    }
}

• Subtask 1: 0 / 28
• Subtask 2: 0 / 72