제출 #1182992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182992		ivaziva	Cijanobakterije (COCI21_cijanobakterije)	C++20	70 / 70	57 ms	15304 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define MAXN 100001

int n,m,brkomp=0;
vector<int> adj[MAXN];
vector<int> nodes[MAXN];
int dist[MAXN];bool pos[MAXN];
queue<int> bfsq;

void dfs(int node,int pret)
{
    nodes[brkomp].push_back(node);pos[node]=true;
    for (int sled:adj[node])
    {
        if (sled!=pret) dfs(sled,node);
    }
}

void bfs(int komp,int pret)
{
    for (int node:nodes[komp]) dist[node]=INT_MAX;
    dist[pret]=0;bfsq.push(pret);
    while (!bfsq.empty())
    {
        int node=bfsq.front();bfsq.pop();
        for (int sled:adj[node])
        {
            if (dist[sled]!=INT_MAX) continue;
            dist[sled]=dist[node]+1;bfsq.push(sled);
        }
    }
}

int main()
{
    cin>>n>>m;int ans=0;
    for (int i=1;i<=m;i++) {int x,y;cin>>x>>y;adj[x].push_back(y);adj[y].push_back(x);}
    for (int node=1;node<=n;node++)
    {
        if (!pos[node]) {brkomp++;dfs(node,0);}
    }
    for (int komp=1;komp<=brkomp;komp++)
    {
        bfs(komp,nodes[komp][0]);int maxdist=0,maxnode=nodes[komp][0];
        for (int node:nodes[komp])
        {
            if (dist[node]>maxdist) {maxdist=dist[node];maxnode=node;}
        }
        bfs(komp,maxnode);maxdist=0;
        for (int node:nodes[komp]) maxdist=max(maxdist,dist[node]);
        ans+=maxdist+1;
    }
    cout<<ans<<endl;
}

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