Submission #679394

#	Time	Username	Problem	Language	Result	Execution time	Memory
679394		Warinchai	Cijanobakterije (COCI21_cijanobakterije)	C++14	70 / 70	118 ms	23756 KiB

Main

#include<bits/stdc++.h>
using namespace std;
vector<int>v[100005];
int p[100005];
int soch[100005][2];
bool vis[100005];
priority_queue<int>pq[100005];
vector<int>pr;
int mxl[100005];
int dfs(int nd,int par){
	for(int i=0;i<v[nd].size();i++){
		if(vis[v[nd][i]]==0){
			vis[v[nd][i]]=1;
			pq[nd].push(dfs(v[nd][i],par));
		}
	}
	if(!pq[nd].empty()){
		soch[nd][0]=pq[nd].top();
		pq[nd].pop();
	}
	if(!pq[nd].empty()){
		soch[nd][1]=pq[nd].top();
	}
	if(soch[nd][0]+soch[nd][1]+1>mxl[par]){
		mxl[par]=soch[nd][0]+soch[nd][1]+1;
	}
	return soch[nd][0]+1;
}
int fp(int a){
	if(p[a]==a){
		return a;
	}
	p[a]=fp(p[a]);
	return p[a];
}
void un(int a,int b){
	if(fp(a)==fp(b)){
		return;
	}
	p[fp(a)]=fp(b);
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		p[i]=i;
	}
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
		un(a,b);
	}
	for(int i=1;i<=n;i++){
		if(fp(i)==i){
			pr.push_back(i);
		}
	}
	int ans=0;
	for(int i=0;i<pr.size();i++){
		int nd=pr[i];
		vis[nd]=1;
		dfs(nd,nd);
		ans+=mxl[nd];
	}
	cout<<ans;
}

Compilation message (stderr)

Main.cpp: In function 'int dfs(int, int)':
Main.cpp:11:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i=0;i<v[nd].size();i++){
      |              ~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0;i<pr.size();i++){
      |              ~^~~~~~~~~~

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