oj.uz

Submission #577162

# Submission time Handle Problem Language Result Execution time Memory
577162 2022-06-14T08:15:02 Z eecs Mountains and Valleys (CCO20_day1problem3) C++17
2 / 25
 663 ms 12648 KB 
#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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 605 ms 12564 KB Output is correct
2 Correct 576 ms 12648 KB Output is correct
3 Correct 606 ms 12516 KB Output is correct
4 Correct 601 ms 12496 KB Output is correct
5 Correct 612 ms 12500 KB Output is correct
6 Correct 138 ms 12492 KB Output is correct
7 Correct 593 ms 12564 KB Output is correct
8 Correct 663 ms 12512 KB Output is correct
9 Correct 571 ms 12540 KB Output is correct
10 Correct 580 ms 12500 KB Output is correct
11 Correct 564 ms 12536 KB Output is correct
12 Correct 591 ms 12492 KB Output is correct
13 Correct 561 ms 12628 KB Output is correct
14 Correct 569 ms 12516 KB Output is correct

Subtask #4
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -