oj.uz

Submission #731105

# Submission time Handle Problem Language Result Execution time Memory
731105 2023-04-27T01:46:41 Z beaboss Hard route (IZhO17_road) C++14
0 / 100
 9 ms 14312 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;
ll n;
vector<ll> adj[N];
ll maxoutdist[N];
ll out[N];
ll maxi = 0;
ll nummaxi = 0;
ll h[N];

void update(ll ans, ll numways) {
	if (ans > maxi) {
		maxi = ans;
		nummaxi = numways;
	} else if (ans == maxi) nummaxi += numways;
}
map<ll, vector<int>> cntheights[N];
void dfs4(ll cur, ll p) {
	for (auto val: adj[cur]) {
		if (val != p) {
			dfs4(val, cur);
			int sum = 0;
			for (auto e: cntheights[val][h[val]]) sum+=e;
			cntheights[cur][h[val] + 1].pb(sum);
		}
	}
	if (adj[cur].size() == 1) cntheights[cur][0].pb(1);
}


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


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

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

	
	if (heights.size() >= 3) {
		// cout << cur << heights[0] << heights[1] << heights[2] << endl;
		ll numways = 0;
		// cntheights[heights[0]]--;
		int sum = 0;
		if (heights[1]==heights[2]) {
			for (auto val: cntheights[cur][heights[1]]) sum += val;
			for (auto val: cntheights[cur][heights[1]]) numways += val * (sum - val);	
			numways/=2;
			// numways = (cntheights[heights[1]] * (cntheights[heights[1]] - 1ll)/2ll);
		}
		else numways = (cntheights[cur][heights[1]].size() * (cntheights[cur][heights[2]].size()));

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

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

void dfs0(ll cur, ll p) {
	// cout << cur << endl;
	vector<ll> 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) {
			ll 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);
		}
	}

}


void dfs(ll cur, ll p) { // get all heights
	vector<ll> heights;
	map<ll, ll> 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);
	dfs4(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 7 ms 14312 KB Output is correct
2 Correct 9 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Incorrect 8 ms 14292 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14312 KB Output is correct
2 Correct 9 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Incorrect 8 ms 14292 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14312 KB Output is correct
2 Correct 9 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Incorrect 8 ms 14292 KB Output isn't correct
5 Halted 0 ms 0 KB -