oj.uz

답안 #577162

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 12060 KB Output isn't correct
2 Halted 0 ms 0 KB -