Submission #577162

#	Time	Username	Problem	Language	Result	Execution time	Memory
577162		eecs	Mountains and Valleys (CCO20_day1problem3)	C++17	2 / 25	663 ms	12648 KiB

Main

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

const int maxn = 500010;
int n, m;
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 E.push_back({w, u, v});
    }
    int diam = 0;
    for (int i = 1; i <= n; i++) {
        auto dfs = [&](auto self, int u, int fa, int d) -> void {
            diam = max(diam, d);
            for (int v : G[u]) if (v ^ fa) self(self, v, u, d + 1);
        };
        dfs(dfs, i, 0, 0);
    }
    int ans = 2 * (n - 1) - diam;
    cout << ans << "\n";
    return 0;
}

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