oj.uz

Submission #1042980

# Submission time Handle Problem Language Result Execution time Memory
1042980 2024-08-03T16:42:00 Z pubin06 Hard route (IZhO17_road) C++14
19 / 100
 6 ms 14600 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define sz(v) (int)(v).size()
#define pii pair<int, int>
using namespace std;

const int MXn = 500005;

void make_better(int &A, int &B, int x, int y) {
	if (A < x) {
		A = x;
		B = y;
	} else if (A == x) {
		B += y;
	}
}
pii get_better(int A, int B, int x, int y) {
	if (A < x) {
		A = x;
		B = y;
	} else if (A == x) {
		B += y;
	}
	return {A, B};
}

int n;
vector<int> adj[MXn];
int mx[MXn], cnt[MXn];
void DFS1(int u, int par) {
	mx[u] = 0, cnt[u] = 1;
	for (int v: adj[u]) if (v != par) {
		DFS1(v, u);
		make_better(mx[u], cnt[u], mx[v] + 1, cnt[v]);
	}
}
int H = 0, dem = 1;
void DFS2(int u, int par, int Mx, int Cnt) {
	vector<tuple<int, int, int>> nah;
	vector<pii> paths;
	if (Mx) {
		paths.emplace_back(Mx, Cnt);
	}
	for (int v: adj[u]) if (v != par) {
		nah.emplace_back(v, mx[v] + 1, cnt[v]);
		paths.emplace_back(mx[v] + 1, cnt[v]);
	}
	sort(begin(paths), end(paths), greater<pii>());
	if (sz(paths) >= 3) {
		int z = paths[0].fi, y = paths[1].fi, x = paths[2].fi;
		int h = z * (x + y);
		if (H <= h) {
			int Dz = paths[0].se, Dy = paths[1].se, Dx = paths[2].se;
			for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) Dx += paths[i].se;
			int Dem = 0;
			if (x < y && y < z) {
				Dem = Dx * Dy;
			} else if (x == y && y < z) {
				Dem = ((Dx + Dy) * (Dx + Dy - 1) / 2);
			} else if (x < y && y == z) {
				Dem = Dx * (Dy + Dz);
			} else if (x == y && y == z) {
				int tmp = Dx + Dy + Dz;
				Dem = tmp * (tmp - 1) / 2;
			}
			make_better(H, dem, h, Dem);
		}
	}
	
	vector<pii> s;
	if (sz(nah)) {
		s.resize(sz(nah));
		s.back() = {(get<1>(nah.back())) + 1, get<2>(nah.back())};
		for (int i = sz(nah) - 2; i >= 0; i--) {
			s[i] = get_better(s[i + 1].fi, s[i + 1].se, (get<1>(nah[i])) + 1, get<2>(nah[i]));
		}
	}
	pii p = {Mx + 1, Cnt};
	for (int i = 0; i < sz(nah); i++) {
		pii New = p;
		if (i != sz(nah) - 1) New = get_better(New.fi, New.se, s[i + 1].fi, s[i + 1].se);
		DFS2(get<0>(nah[i]), u, New.fi, New.se);
		p = get_better(p.fi, p.se, (get<1>(nah[i])) + 1, get<2>(nah[i]));
	}
}

signed main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	
	DFS1(1, 0);
	DFS2(1, 0, 0, 1);
	cout << H << ' ' << dem;
	
	return 0;
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13656 KB Output is correct
2 Correct 5 ms 13660 KB Output is correct
3 Correct 4 ms 13660 KB Output is correct
4 Correct 4 ms 13660 KB Output is correct
5 Correct 4 ms 13660 KB Output is correct
6 Correct 4 ms 13656 KB Output is correct
7 Correct 4 ms 13660 KB Output is correct
8 Correct 4 ms 13660 KB Output is correct
9 Correct 4 ms 13660 KB Output is correct
10 Correct 4 ms 13552 KB Output is correct
11 Correct 5 ms 13660 KB Output is correct
12 Correct 5 ms 13660 KB Output is correct
13 Correct 4 ms 13496 KB Output is correct
14 Correct 3 ms 13660 KB Output is correct
15 Correct 4 ms 13728 KB Output is correct
16 Correct 4 ms 13660 KB Output is correct
17 Correct 3 ms 13660 KB Output is correct
18 Correct 4 ms 13656 KB Output is correct
19 Correct 3 ms 13656 KB Output is correct
20 Correct 4 ms 13656 KB Output is correct
21 Correct 3 ms 13664 KB Output is correct
22 Correct 4 ms 13660 KB Output is correct
23 Correct 4 ms 13660 KB Output is correct
24 Correct 3 ms 13660 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13656 KB Output is correct
2 Correct 5 ms 13660 KB Output is correct
3 Correct 4 ms 13660 KB Output is correct
4 Correct 4 ms 13660 KB Output is correct
5 Correct 4 ms 13660 KB Output is correct
6 Correct 4 ms 13656 KB Output is correct
7 Correct 4 ms 13660 KB Output is correct
8 Correct 4 ms 13660 KB Output is correct
9 Correct 4 ms 13660 KB Output is correct
10 Correct 4 ms 13552 KB Output is correct
11 Correct 5 ms 13660 KB Output is correct
12 Correct 5 ms 13660 KB Output is correct
13 Correct 4 ms 13496 KB Output is correct
14 Correct 3 ms 13660 KB Output is correct
15 Correct 4 ms 13728 KB Output is correct
16 Correct 4 ms 13660 KB Output is correct
17 Correct 3 ms 13660 KB Output is correct
18 Correct 4 ms 13656 KB Output is correct
19 Correct 3 ms 13656 KB Output is correct
20 Correct 4 ms 13656 KB Output is correct
21 Correct 3 ms 13664 KB Output is correct
22 Correct 4 ms 13660 KB Output is correct
23 Correct 4 ms 13660 KB Output is correct
24 Correct 3 ms 13660 KB Output is correct
25 Correct 6 ms 14172 KB Output is correct
26 Incorrect 5 ms 14600 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 13656 KB Output is correct
2 Correct 5 ms 13660 KB Output is correct
3 Correct 4 ms 13660 KB Output is correct
4 Correct 4 ms 13660 KB Output is correct
5 Correct 4 ms 13660 KB Output is correct
6 Correct 4 ms 13656 KB Output is correct
7 Correct 4 ms 13660 KB Output is correct
8 Correct 4 ms 13660 KB Output is correct
9 Correct 4 ms 13660 KB Output is correct
10 Correct 4 ms 13552 KB Output is correct
11 Correct 5 ms 13660 KB Output is correct
12 Correct 5 ms 13660 KB Output is correct
13 Correct 4 ms 13496 KB Output is correct
14 Correct 3 ms 13660 KB Output is correct
15 Correct 4 ms 13728 KB Output is correct
16 Correct 4 ms 13660 KB Output is correct
17 Correct 3 ms 13660 KB Output is correct
18 Correct 4 ms 13656 KB Output is correct
19 Correct 3 ms 13656 KB Output is correct
20 Correct 4 ms 13656 KB Output is correct
21 Correct 3 ms 13664 KB Output is correct
22 Correct 4 ms 13660 KB Output is correct
23 Correct 4 ms 13660 KB Output is correct
24 Correct 3 ms 13660 KB Output is correct
25 Correct 6 ms 14172 KB Output is correct
26 Incorrect 5 ms 14600 KB Output isn't correct
27 Halted 0 ms 0 KB -