제출 #863230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
863230		TAhmed33	Cijanobakterije (COCI21_cijanobakterije)	C++98	70 / 70	58 ms	16076 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 25;
vector <int> adj[MAXN];
int dp[MAXN][2];
bool vis[MAXN];
void dfs (int pos, int par) {
	vis[pos] = 1;
	int mx1 = 0, mx2 = 0, mx3 = 0;
	for (auto j : adj[pos]) {
		if (j == par) continue;
		dfs(j, pos);
		if (1 + dp[j][1] > mx1) {
			mx2 = mx1; mx1 = dp[j][1];
		} else if (dp[j][1] > mx2) {
			mx2 = dp[j][1];
		}
		mx3 = max(mx3, dp[j][0]);
	}	
	dp[pos][0] = max(1 + mx1 + mx2, mx3);
	dp[pos][1] = 1 + mx1;
}
int main () {
	int mx = 0;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			dfs(i, -1);
			mx += dp[i][0]; 
		}
	}
	cout << mx << '\n';
}

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