제출 #746479

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

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int x,k;
vector<int>v[N];
int dist[N][2];
bool vis[N][2];
pair<int,int>dfs(int i,bool f){
	queue<int>q;
	q.push(i);
	vis[i][f]=1;
	dist[i][f]=1;
	int mx=0,pos=i;
	while(q.size()){
		int j=q.front();q.pop();
		if(mx<dist[j][f]){
			mx=dist[j][f];
			pos=j;
		}
		for(auto c:v[j]){
			if(vis[c][f])continue;
			vis[c][f]=1;
			dist[c][f]=dist[j][f]+1;
			q.push(c);
		}
	}
	return {pos,mx};
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>x>>k;
	for(int i=0;i<k;i++){
		int l,r;cin>>l>>r;
		v[l].push_back(r);
		v[r].push_back(l);
	}
	int ans=0;
	for(int i=1;i<=x;i++){
		if(vis[i][0])continue;
		int c=dfs(i,0).first;
		ans+=dfs(c,1).second;
	}
	cout<<ans;
	return 0;
}

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