Submission #529018

#	Time	Username	Problem	Language	Result	Execution time	Memory
529018		penguinhacker	Cijanobakterije (COCI21_cijanobakterije)	C++14	70 / 70	37 ms	13232 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1e5;
int n, m;
vector<int> adj[mxN];
bool vis[mxN];

ar<int, 2> dfs(int u) {
	vis[u]=1;
	ar<int, 2> d={};
	int diam=0;
	for (int v : adj[u])
		if (!vis[v]) {
			ar<int, 2> x=dfs(v);
			diam=max(diam, x[0]);
			if (x[1]+1>d[0]) {
				swap(d[0], d[1]);
				d[0]=x[1]+1;
			} else if (x[1]+1>d[1])
				d[1]=x[1]+1;
		}
	diam=max(diam, d[0]+d[1]);
	return {diam, d[0]};
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<m; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int ans=0;
	for (int i=0; i<n; ++i)
		if (!vis[i])
			ans+=dfs(i)[0]+1;
	cout << ans;
	return 0;
}

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