oj.uz

Submission #863226

# Submission time Handle Problem Language Result Execution time Memory
863226 2023-10-19T20:22:29 Z TAhmed33 Cijanobakterije (COCI21_cijanobakterije) C++
12 / 70
 61 ms 16780 KB 
#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;
	for (auto j : adj[pos]) {
		if (j == par) continue;
		dfs(j, pos);
		if (1 + dp[j][1] > mx1) {
			mx2 = mx1; mx1 = 1 + dp[j][1];
		} else if (1 + dp[j][1] > mx2) {
			mx2 = 1 + dp[j][1];
		}
	}	
	dp[pos][0] = mx1 + mx2;
	dp[pos][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 += 1 + dp[i][0];
		}
	}
	cout << mx << '\n';
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 16780 KB Output is correct
2 Correct 5 ms 3932 KB Output is correct
3 Correct 9 ms 4472 KB Output is correct
4 Correct 13 ms 4956 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3416 KB Output is correct
4 Correct 1 ms 3416 KB Output is correct
5 Correct 6 ms 4184 KB Output is correct
6 Correct 11 ms 4700 KB Output is correct
7 Correct 16 ms 5468 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4188 KB Output isn't correct
2 Halted 0 ms 0 KB -