Submission #1108092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108092		overwatch9	Cijanobakterije (COCI21_cijanobakterije)	C++17	70 / 70	52 ms	11852 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 1;
vector <int> adj[maxn];
bool vis[maxn];
int node = 0, max_dis = -1;
void dfs(int s, int p, int d) {
    if (d > max_dis) {
        node = s;
        max_dis = d;
    }
    vis[s] = true;
    for (auto i : adj[s]) {
        if (i == p)
            continue;
        dfs(i, s, d+1);
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector <pair <int, int>> endpoints;
    for (int i = 1; i <= n; i++) {
        if (vis[i])
            continue;
        max_dis = -1;
        endpoints.emplace_back();
        dfs(i, i, 0);
        endpoints.back().first = node;
        max_dis = -1;
        dfs(node, node, 0);
        endpoints.back().second = node;
    }

    for (int i = 0; i + 1 < (int)endpoints.size(); i++) {
        int a = endpoints[i].second, b = endpoints[i+1].first;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    max_dis = -1;
    dfs(endpoints.back().second, 0, 0);
    cout << max_dis+1 << '\n';

}

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 15 / 15
• Subtask 5: 28 / 28