Submission #577205

#	Time	Username	Problem	Language	Result	Execution time	Memory
577205		eecs	Mountains and Valleys (CCO20_day1problem3)	C++17	11 / 25	7018 ms	197012 KiB

Main

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

const int maxn = 5010;
int n, m, d[maxn][maxn], par[maxn][maxn];
vector<int> G[maxn];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    assert(n <= 5000 && m <= 10000);
    vector<array<int, 3>> E;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        if (w == 1) G[u].push_back(v), G[v].push_back(u);
        else if (w < (n + 1) / 2) E.push_back({u, v, w});
    }
    int diam = 0;
    for (int i = 0; i < n; i++) {
        auto dfs = [&](auto self, int u, int fa) -> void {
            diam = max(diam, d[i][u]), par[i][u] = fa;
            for (int v : G[u]) if (v ^ fa) {
                d[i][v] = d[i][u] + 1, self(self, v, u);
            }
        };
        dfs(dfs, i, -1);
    }
    int ans = 2 * (n - 1) - diam;
    for (auto &e : E) {
        int u = e[0], v = e[1], mn = INT_MAX;
        for (int i = 0; i < n; i++) if (i ^ u) {
            for (int j = 0; j < n; j++) if (j ^ v) {
                int cnt = 0;
                for (int k = 0; k < n; k++) {
                    if (d[u][k] + d[k][i] == d[u][i] && d[v][k] + d[k][j] == d[v][j]) cnt++;
                }
                mn = min(mn, 2 * (n + cnt - 2) - d[u][i] - d[v][j]);
            }
        }
        ans = min(ans, mn + e[2]);
    }
    cout << ans << "\n";
    return 0;
}

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