oj.uz

Submission #899431

# Submission time Handle Problem Language Result Execution time Memory
899431 2024-01-06T07:23:13 Z TAhmed33 Hard route (IZhO17_road) C++
0 / 100
 7 ms 23900 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
const int MAXN = 5e5 + 25;
vector <int> adj[MAXN];
vector <int> dp[MAXN];
int n;
int mx = 0, cnt = 0;
void upd (int x) {
	if (x > mx) {
		mx = x; cnt = 1;
	} else if (x == mx) cnt++;
}
void dfs (int pos, int par, int dep = 0) {
	dp[pos].clear();
	if (adj[pos].size() == 1 && par != -1) {
		dp[pos].push_back(0);
		upd(0);
		return;
	}
	for (auto j : adj[pos]) {
		if (j == par) continue;
		dfs(j, pos, dep + 1);
		for (auto i : dp[j]) {
			dp[pos].push_back(i + 1);
		}
	}
	sort(dp[pos].begin(), dp[pos].end());
	reverse(dp[pos].begin(), dp[pos].end());
	if (dp[pos].size() > 1) {
		upd((dep + dp[pos][0]) * dp[pos][1]);
		upd((dep + dp[pos][1]) * dp[pos][0]);
	}
	//cout << pos << " " << par << " " << dep << ": "; for (auto j : dp[pos]) cout << j << " ";
	//cout << '\n';
	dp[pos].resize(1);
}	
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; 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 (adj[i].size() == 1) {
			//cout << "            " << i << ": \n";
			dfs(i, -1);
		}
	}
	cout << mx << " " << cnt / 2 << '\n';
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23900 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Correct 6 ms 23896 KB Output is correct
4 Correct 5 ms 23900 KB Output is correct
5 Correct 5 ms 23900 KB Output is correct
6 Correct 5 ms 23892 KB Output is correct
7 Incorrect 5 ms 23900 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23900 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Correct 6 ms 23896 KB Output is correct
4 Correct 5 ms 23900 KB Output is correct
5 Correct 5 ms 23900 KB Output is correct
6 Correct 5 ms 23892 KB Output is correct
7 Incorrect 5 ms 23900 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 23900 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Correct 6 ms 23896 KB Output is correct
4 Correct 5 ms 23900 KB Output is correct
5 Correct 5 ms 23900 KB Output is correct
6 Correct 5 ms 23892 KB Output is correct
7 Incorrect 5 ms 23900 KB Output isn't correct
8 Halted 0 ms 0 KB -