Submission #282337

#	Time	Username	Problem	Language	Result	Execution time	Memory
282337		imeimi2000	Mountains and Valleys (CCO20_day1problem3)	C++17	25 / 25	3118 ms	214096 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

int n, m;
int X[2000001], Y[2000001], W[2000001];
vector<int> edge[500001];

namespace TSP {
    llong dp[1 << 20][20];
    llong dist[20][20];
    llong solve() {
        memset(dist, 0x3f, sizeof(dist));
        for (int i = 1; i <= m; ++i) {
            int x, y, w;
            cin >> x >> y >> w;
            dist[x][y] = dist[y][x] = min(dist[x][y], 1ll * w);
        }
        for (int i = 0; i < n; ++i) dist[i][i] = 0;
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        memset(dp, 0x3f, sizeof(dp));
        for (int i = 0; i < n; ++i) dp[1 << i][i] = 0;
        for (int i = 0; i < (1 << n); ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i >> j) & 1) for (int k = 0; k < n; ++k) {
                    if ((i >> k) & 1) continue;
                    dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + dist[j][k]);
                }
            }
        }
        return *min_element(dp[(1 << n) - 1], dp[(1 << n) - 1] + n);
    }
}

template <int T>
struct save_max {
    int val[T], idx[T];
    void init(int v = 0) {
        memset(val, v, sizeof(val));
        memset(idx, 0, sizeof(idx));
    }
    void save(int v, int i) {
        for (int j = 0; j < T; ++j) {
            if (val[j] >= v) continue;
            for (int k = T - 1; k > j; --k) {
                val[k] = val[k - 1];
                idx[k] = idx[k - 1];
            }
            val[j] = v;
            idx[j] = i;
            break;
        }
    }
    void add(int x) {
        for (int i = 0; i < T; ++i) val[i] += x;
    }
    int get(int idx1 = -1, int idx2 = -1) const {
        for (int i = 0; i < T; ++i) {
            if (idx[i] == idx1 || idx[i] == idx2) continue;
            return val[i];
        }
        printf("get(%d, %d), idx[0] = %d\n", idx1, idx2, idx[0]);
        exit(1);
    }
    int get2(int idx1 = -1, int idx2 = -1) {
        int cnt = 2, sum = 0;
        for (int i = 0; i < T && cnt; ++i) {
            if (idx[i] == idx1 || idx[i] == idx2) continue;
            --cnt, sum += val[i];
        }
        if (cnt) printf("get(%d, %d), idx[0] = %d", idx1, idx2, idx[0]), exit(2);
        return sum;
    }
};

bool del[500001];
save_max<4> dis_down[500001];
save_max<3> dis_maxd[500001];

void dfs2(int x, int p) {
    for (int i : edge[x]) {
        if (i == p) continue;
        if (!del[i]) dfs2(i, x);
        dis_down[x].save(dis_down[i].get(x) + 1, i);
        dis_maxd[x].save(max(dis_down[i].get2(x), dis_maxd[i].get(x)), i);
    }
}

save_max<1> dis_toup[500001];
save_max<1> dis_maxu[500001];
save_max<1> dis_root[500001];
int subtree[500001], dep[500001];

int disu[500001], dism[500001], disd[500001];
void dfs3(int x, int p) {
    dep[x] = dep[p] + 1;
    for (int i : edge[x]) {
        if (i == p || del[i]) continue;
        dis_toup[i].save(dis_toup[x].get() - 1, x);
        dis_toup[i].save(dis_down[x].get(i) - 1, x);
        dis_maxu[i].save(dis_maxu[x].get(), x);
        dis_maxu[i].save(dis_down[x].get2(i), x);
        dis_maxu[i].save(dis_down[x].get(i) + dis_toup[x].get(), x);
        dis_root[i].save(dis_root[x].get(), x);
        dis_root[i].save(dis_down[x].get(i) - dep[x], x);
        subtree[i] = subtree[x];
        disu[i] = max(disu[x], dep[x] + dis_down[x].get(i));
        dism[i] = max(dism[x], disu[p] - dep[x] + dis_down[x].get(i));
        disd[i] = max(disd[x], dis_down[x].get(i)) + 1;
        dfs3(i, x);
    }
    dis_root[x].save(dis_down[x].get() - dep[x], x);
    dism[x] = max(dism[x], disu[x] - dep[x] + dis_down[x].get());
    disd[x] = max(disd[x], dis_down[x].get()) - dep[x];
}


vector<int> qs[500001];
int ans;
void solve(int x) {
    dfs2(x, 0);
    subtree[x] = -1;
    dep[x] = 0;
    for (int i : edge[x]) {
        if (del[i]) continue;
        subtree[i] = i;
        disu[i] = 0;
        dism[i] = -1e8;
        disd[i] = 0;
        dfs3(i, x);
    }
    for (int i : qs[x]) {
        int a = X[i], b = Y[i];
        int sa = subtree[a], sb = subtree[b];
        if (sa == sb) continue;
        int d = max(dis_down[x].get2(sa, sb), dis_maxd[x].get(sa, sb));
        int d1 = dis_down[x].get(sa, sb);
        int d2 = a != x ? dis_root[a].get() : 0;
        int d3 = b != x ? dis_root[b].get() : 0;
        d = max({ d, d1 + d2, d2 + d3, d3 + d1 });
        for (int j : { a, b }) if (j != x) {
            d = max({ d, dis_maxd[j].get(), dis_down[j].get2(), dis_maxu[j].get(), dis_down[j].get() + dis_toup[j].get() });
            d = max(d, 2 + max(dism[j], dis_down[x].get(sa, sb) + max(dism[j], dis_down[j].get() - dep[j])));
        }
        ans = min(ans, 2 * n - 2 - dep[a] - dep[b] - d + W[i]);
    }
}

int sz[500001];
void dfs1(int x, int p) {
    dis_down[x].init();
    dis_maxd[x].init();
    dis_toup[x].init();
    dis_maxu[x].init();
    dis_root[x].init();
    sz[x] = 1;
    for (int i : edge[x]) {
        if (i == p || del[i]) continue;
        dfs1(i, x);
        sz[x] += sz[i];
    }
}

void centroid(int x) {
    vector<int> &idx = qs[x];
    if (idx.empty()) return;
    dfs1(x, 0);
    {
        int p = 0, s = sz[x];
        for (bool loop = 0; !loop; loop ^= 1) {
            for (int i : edge[x]) {
                if (i == p || del[i]) continue;
                if (sz[i] * 2 > s) {
                    p = x;
                    x = i;
                    loop = 1;
                    break;
                }
            }
        }
    }
    swap(idx, qs[x]);
    solve(x);
    del[x] = 1;
    for (int i : qs[x]) {
        if (subtree[X[i]] == subtree[Y[i]]) qs[subtree[X[i]]].push_back(i);
    }
    qs[x].clear();
    qs[x].shrink_to_fit();
    for (int i : edge[x]) {
        if (del[i]) continue;
        centroid(i);
    }
}

int main() {
#ifdef imeimi
    //freopen("oi/cco20/3.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
#ifndef imeimi
    if (n <= 20) return printf("%lld\n", TSP::solve()), 0;
#endif
    for (int i = 1; i <= m; ++i) {
        cin >> X[i] >> Y[i] >> W[i];
        ++X[i], ++Y[i];
        if (W[i] > 1) {
            qs[1].push_back(i);
            continue;
        }
        edge[X[i]].push_back(Y[i]);
        edge[Y[i]].push_back(X[i]);
    }
    dfs2(1, 0);
    ans = 2 * n - 2 - max(dis_maxd[1].get(), dis_down[1].get2());
    centroid(1);
    printf("%d\n", ans);
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 6 / 6
• Subtask 5: 2 / 2
• Subtask 6: 3 / 3
• Subtask 7: 5 / 5
• Subtask 8: 4 / 4