Submission #638842

#	Time	Username	Problem	Language	Result	Execution time	Memory
638842		NotLinux	Cijanobakterije (COCI21_cijanobakterije)	C++14	70 / 70	65 ms	15436 KiB

Main

/**
 * author: NotLinux
 * created: 07.09.2022 ~ 18:41:58
**/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef LOCAL
    #include "/home/notlinux/debug.h"
#else
    #define debug(x...) void(37)
#endif
vector < vector < int > > graph;
vector < int > par;
vector < int > vis;
vector < int > visdsu;
pair < int , int >  dfs(int node , int past){
    pair < int , int > ret = {node,1};
    for(auto itr : graph[node]){
        if(itr == past)continue;
        pair < int , int > dumb = dfs(itr,node);
        debug(itr,node,dumb);
        if(ret.second < (dumb.second+1)){
            ret = {dumb.first , dumb.second+1};
        }
    }
    return {ret.first , ret.second};
}
int longest_path(int st){
    debug(st);
    int node1 = dfs(st,0).first;
    debug(node1);
    int rams = dfs(node1,0).second;
    debug(st,rams);
    return rams;
}
int find(int a){
    if(par[a] == a)return a;    
    par[a] = find(par[a]);
    return par[a];
}
void merge(int a, int b){
    par[find(a)] = find(b);
}
void solve(){
    int n,m;cin >> n >> m;

    par.resize(n+1);
    iota(par.begin(),par.end(),0LL);
    graph.resize(n+1);
    vis.resize(n+1);
    visdsu.resize(n+1);

    while(m--){
        int a,b;cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        merge(a,b);
    }
    int ans = 0;
    for(int i = 1;i<=n;i++){
        if(visdsu[find(i)] == 0){
            ans += longest_path(i);
            visdsu[find(i)] = 1;
        }
    }
    cout << ans << endl;
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    int tt=1;
    //cin >> tt;
    while(tt--)solve();
}

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