oj.uz

Submission #1089851

# Submission time Handle Problem Language Result Execution time Memory
1089851 2024-09-17T10:04:04 Z toast12 Cijanobakterije (COCI21_cijanobakterije) C++14
15 / 70
 24 ms 6452 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int n;
vector<bool> visited;
vector<vector<int>> adj;
vector<int> dist;
queue<int> q;

pair<int, int> diameter(int start) {
    q.push(start);
    vector<bool> v(n+1);
    dist[start] = 0;
    int a1 = 0, a2 = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (dist[cur] > a1) {
            a1 = dist[cur];
            a2 = cur;
        }
        visited[cur] = true;
        for (auto e : adj[cur]) {
            if (!v[e]) {
                dist[e] = dist[cur]+1;
                q.push(e);
                v[e] = true;
            }
        }
    }
    return {a1, a2};
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int m;
    cin >> n >> m;
    adj.resize(n+1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; 
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    visited.resize(n+1);
    dist.resize(n+1, INF);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            int x = diameter(i).second;
            ans += diameter(x).first;
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1368 KB Output is correct
2 Correct 9 ms 2396 KB Output is correct
3 Correct 13 ms 3420 KB Output is correct
4 Correct 16 ms 4464 KB Output is correct
5 Correct 19 ms 5360 KB Output is correct
6 Correct 24 ms 6452 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6232 KB Output is correct
2 Incorrect 4 ms 1116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1368 KB Output is correct
2 Correct 9 ms 2396 KB Output is correct
3 Correct 13 ms 3420 KB Output is correct
4 Correct 16 ms 4464 KB Output is correct
5 Correct 19 ms 5360 KB Output is correct
6 Correct 24 ms 6452 KB Output is correct
7 Correct 19 ms 6232 KB Output is correct
8 Incorrect 4 ms 1116 KB Output isn't correct
9 Halted 0 ms 0 KB -