oj.uz

Submission #731082

# Submission time Handle Problem Language Result Execution time Memory
731082 2023-04-27T00:43:15 Z beaboss Hard route (IZhO17_road) C++14
0 / 100
 4 ms 5000 KB 
#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;

const ll INF = 1e17 + 10ll;
const ll N = 2*1e5 + 10;
int n;
vector<int> adj[N];
int maxoutdist[N];
int out[N];
int maxi = 0;
int nummaxi = 0;
int h[N];

void update(int ans, int numways) {
	if (ans > maxi) {
		maxi = ans;
		nummaxi = numways;
	} else if (ans == maxi) nummaxi += numways;
}

void dfs1(int cur, int p) {
	vector<int> heights;
	map<int, int> cntheights;
	for (auto val: adj[cur]) {
		if (val != p) {
			heights.pb(h[val] + 1);
			cntheights[h[val] + 1]++;
		}
	}


	heights.pb(out[cur]);
	cntheights[out[cur]]++;

	sort(heights.rbegin(), heights.rend());

	// cout << cur << heights[0] << heights[1] << heights[2] << endl;
	if (heights.size() >= 3) {
		int numways = 1;
		numways *= cntheights[heights[0]];
		cntheights[heights[0]]--;
		if (heights[1]==heights[2]) numways *= (cntheights[heights[1]] * (cntheights[heights[1]] - 1)/2);
		else numways *= (cntheights[heights[1]] * (cntheights[heights[2]]));

		update(heights[0] * (heights[1] + heights[2]), numways);

	}

	for (auto val: adj[cur]) {
		if (val != p) dfs1(val, cur);
	}
}

void dfs0(int cur, int p) {
	// cout << cur << endl;
	vector<int> heights ={0, 0, 0};
	for (auto val: adj[cur]) if (val != p) heights.pb(h[val] + 2);

	sort(heights.rbegin(), heights.rend());

	for (auto val: adj[cur]) {
		if (val != p) {
			int curopt = heights[0];
			if (h[val] + 2 == curopt) curopt = heights[1];
			if (curopt < out[cur] + 1) {
				curopt = out[cur]+1;
			}
			out[val] = max(out[val], curopt);
			dfs0(val, cur);
		}
	}

	// cout << cur << out[cur] << endl;

}


void dfs(int cur, int p) { // get all heights
	vector<int> heights;
	map<int, int> cntheights;
	for (auto val: adj[cur]) {
		if (val != p) {
			dfs(val, cur);
			h[cur] = max(h[val] + 1, h[cur]);
		}
	}

}


int main() {
	

	cin >> n;

	for (ll i = 0; i < n -1; i++ ) {
		ll a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);

	}
	dfs(1, -1);
	dfs0(1, -1);
	dfs1(1, -1);
	if (maxi == 0) nummaxi = 1;
	cout << maxi << ' ' << nummaxi << endl;



	
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Incorrect 3 ms 5000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Incorrect 3 ms 5000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 4996 KB Output is correct
4 Incorrect 3 ms 5000 KB Output isn't correct
5 Halted 0 ms 0 KB -