Submission #872492

#	Time	Username	Problem	Language	Result	Execution time	Memory
872492		HossamHero7	Cijanobakterije (COCI21_cijanobakterije)	C++14	70 / 70	32 ms	8344 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 1e5+5;
vector<int> adj[N];
int dep[N];
int dep2[N];
int vis[N];
int bfs(int src){
    vis[src] = 1;
    queue<int> q;
    q.push(src);
    pair<int,int> mxDep {0,src};
    while(q.size()){
        int node = q.front();       q.pop();
        for(auto ch : adj[node]){
            if(vis[ch]) continue;
            q.push(ch);
            vis[ch] = 1;
            dep[ch] = dep[node] + 1;
            mxDep = max(mxDep,{dep[ch],ch});
        }
    }
    q.push(mxDep.second);
    vis[mxDep.second] = 2;
    int ret = 1;
    while(q.size()){
        int node = q.front();       q.pop();
        for(auto ch : adj[node]){
            if(vis[ch] == 2) continue;
            q.push(ch);
            vis[ch] = 2;
            dep2[ch] = dep2[node] + 1;
            ret = max(ret , dep2[ch] + 1);
        }
    }
    return ret;
}
void solve(){
    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);
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        ans += bfs(i);
    }
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

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