제출 #878952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878952		Youssif_Elkadi	Cijanobakterije (COCI21_cijanobakterije)	C++17	70 / 70	29 ms	12124 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 5, mod = 1e9 + 7;
int vis[N], vid;
vector<int> adj[N];
int n, m;
pair<int, int> dfs(int u)
{
    vis[u] = vid;
    int node = u, ret = 0;
    for (auto v : adj[u])
    {
        if (vis[v] != vid)
        {
            pair<int, int> tmp = dfs(v);
            if (tmp.first > ret)
                ret = tmp.first, node = tmp.second;
        }
    }
    return {ret + 1, node};
}
int dia(int x)
{
    vid++;
    x = dfs(x).second;
    vid++;
    return dfs(x).first;
}
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int ret = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            ret += dia(i);
    cout << ret << "\n";
}

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