oj.uz

Submission #1043020

# Submission time Handle Problem Language Result Execution time Memory
1043020 2024-08-03T17:50:44 Z pubin06 Hard route (IZhO17_road) C++14
100 / 100
 451 ms 206432 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);
		// cerr << u << ' ' << h;
		if (H <= h) {
			int Dz = paths[0].se, Dy = paths[1].se, Dx = paths[2].se;
			// cerr << ' ' << Dx << ' ' << Dy << ' ' << Dz;
			int Dem = 0;
			if (x < y && y < z) {
				for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) Dx += paths[i].se;
				Dem = Dx * Dy;
			} else if (x == y && y < z) {
				// Dem = ((Dx + Dy) * (Dx + Dy - 1) / 2) - Dx * (Dx - 1) / 2 - Dy * (Dy - 1) / 2;
				Dem = Dy * Dx;
				int tmp = Dy + Dx;
				for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) {
					Dem += tmp * paths[i].se;
					tmp += paths[i].se;
				}
			} else if (x < y && y == z) {
				for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) Dx += paths[i].se;
				Dem = Dx * (Dy + Dz);
			} else if (x == y && y == z) {
				Dem = Dz * Dy + (Dz + Dy) * Dx;
				int tmp = Dx + Dy + Dz;
				for (int i = 3; i < sz(paths); i++) if (paths[i].fi == x) {
					Dem += tmp * paths[i].se;
					tmp += paths[i].se;
				}
			}
			make_better(H, dem, h, Dem);
		}
		// cerr << '\n';
	}
	
	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 2 ms 15704 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 2 ms 15708 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 2 ms 15708 KB Output is correct
6 Correct 2 ms 15708 KB Output is correct
7 Correct 2 ms 15708 KB Output is correct
8 Correct 2 ms 15708 KB Output is correct
9 Correct 4 ms 15556 KB Output is correct
10 Correct 3 ms 15708 KB Output is correct
11 Correct 3 ms 15708 KB Output is correct
12 Correct 2 ms 15708 KB Output is correct
13 Correct 2 ms 15708 KB Output is correct
14 Correct 2 ms 15708 KB Output is correct
15 Correct 2 ms 15708 KB Output is correct
16 Correct 2 ms 15708 KB Output is correct
17 Correct 3 ms 15708 KB Output is correct
18 Correct 3 ms 15704 KB Output is correct
19 Correct 3 ms 15704 KB Output is correct
20 Correct 3 ms 15708 KB Output is correct
21 Correct 3 ms 15708 KB Output is correct
22 Correct 3 ms 15708 KB Output is correct
23 Correct 2 ms 15708 KB Output is correct
24 Correct 3 ms 15708 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15704 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 2 ms 15708 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 2 ms 15708 KB Output is correct
6 Correct 2 ms 15708 KB Output is correct
7 Correct 2 ms 15708 KB Output is correct
8 Correct 2 ms 15708 KB Output is correct
9 Correct 4 ms 15556 KB Output is correct
10 Correct 3 ms 15708 KB Output is correct
11 Correct 3 ms 15708 KB Output is correct
12 Correct 2 ms 15708 KB Output is correct
13 Correct 2 ms 15708 KB Output is correct
14 Correct 2 ms 15708 KB Output is correct
15 Correct 2 ms 15708 KB Output is correct
16 Correct 2 ms 15708 KB Output is correct
17 Correct 3 ms 15708 KB Output is correct
18 Correct 3 ms 15704 KB Output is correct
19 Correct 3 ms 15704 KB Output is correct
20 Correct 3 ms 15708 KB Output is correct
21 Correct 3 ms 15708 KB Output is correct
22 Correct 3 ms 15708 KB Output is correct
23 Correct 2 ms 15708 KB Output is correct
24 Correct 3 ms 15708 KB Output is correct
25 Correct 4 ms 16216 KB Output is correct
26 Correct 7 ms 16476 KB Output is correct
27 Correct 4 ms 16732 KB Output is correct
28 Correct 3 ms 16732 KB Output is correct
29 Correct 4 ms 16524 KB Output is correct
30 Correct 3 ms 16732 KB Output is correct
31 Correct 4 ms 16732 KB Output is correct
32 Correct 4 ms 16476 KB Output is correct
33 Correct 4 ms 16472 KB Output is correct
34 Correct 4 ms 16732 KB Output is correct
35 Correct 4 ms 16732 KB Output is correct
36 Correct 4 ms 16680 KB Output is correct
37 Correct 4 ms 16732 KB Output is correct
38 Correct 4 ms 17500 KB Output is correct
39 Correct 5 ms 16476 KB Output is correct
40 Correct 4 ms 15964 KB Output is correct
41 Correct 4 ms 15964 KB Output is correct
42 Correct 4 ms 15960 KB Output is correct
43 Correct 5 ms 15964 KB Output is correct
44 Correct 3 ms 15964 KB Output is correct
45 Correct 4 ms 15964 KB Output is correct
46 Correct 5 ms 15964 KB Output is correct
47 Correct 4 ms 15964 KB Output is correct
48 Correct 3 ms 16324 KB Output is correct

Subtask #3
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15704 KB Output is correct
2 Correct 3 ms 15708 KB Output is correct
3 Correct 2 ms 15708 KB Output is correct
4 Correct 3 ms 15708 KB Output is correct
5 Correct 2 ms 15708 KB Output is correct
6 Correct 2 ms 15708 KB Output is correct
7 Correct 2 ms 15708 KB Output is correct
8 Correct 2 ms 15708 KB Output is correct
9 Correct 4 ms 15556 KB Output is correct
10 Correct 3 ms 15708 KB Output is correct
11 Correct 3 ms 15708 KB Output is correct
12 Correct 2 ms 15708 KB Output is correct
13 Correct 2 ms 15708 KB Output is correct
14 Correct 2 ms 15708 KB Output is correct
15 Correct 2 ms 15708 KB Output is correct
16 Correct 2 ms 15708 KB Output is correct
17 Correct 3 ms 15708 KB Output is correct
18 Correct 3 ms 15704 KB Output is correct
19 Correct 3 ms 15704 KB Output is correct
20 Correct 3 ms 15708 KB Output is correct
21 Correct 3 ms 15708 KB Output is correct
22 Correct 3 ms 15708 KB Output is correct
23 Correct 2 ms 15708 KB Output is correct
24 Correct 3 ms 15708 KB Output is correct
25 Correct 4 ms 16216 KB Output is correct
26 Correct 7 ms 16476 KB Output is correct
27 Correct 4 ms 16732 KB Output is correct
28 Correct 3 ms 16732 KB Output is correct
29 Correct 4 ms 16524 KB Output is correct
30 Correct 3 ms 16732 KB Output is correct
31 Correct 4 ms 16732 KB Output is correct
32 Correct 4 ms 16476 KB Output is correct
33 Correct 4 ms 16472 KB Output is correct
34 Correct 4 ms 16732 KB Output is correct
35 Correct 4 ms 16732 KB Output is correct
36 Correct 4 ms 16680 KB Output is correct
37 Correct 4 ms 16732 KB Output is correct
38 Correct 4 ms 17500 KB Output is correct
39 Correct 5 ms 16476 KB Output is correct
40 Correct 4 ms 15964 KB Output is correct
41 Correct 4 ms 15964 KB Output is correct
42 Correct 4 ms 15960 KB Output is correct
43 Correct 5 ms 15964 KB Output is correct
44 Correct 3 ms 15964 KB Output is correct
45 Correct 4 ms 15964 KB Output is correct
46 Correct 5 ms 15964 KB Output is correct
47 Correct 4 ms 15964 KB Output is correct
48 Correct 3 ms 16324 KB Output is correct
49 Correct 268 ms 97948 KB Output is correct
50 Correct 287 ms 109512 KB Output is correct
51 Correct 298 ms 119376 KB Output is correct
52 Correct 244 ms 84564 KB Output is correct
53 Correct 243 ms 129348 KB Output is correct
54 Correct 238 ms 142648 KB Output is correct
55 Correct 238 ms 109776 KB Output is correct
56 Correct 249 ms 123988 KB Output is correct
57 Correct 281 ms 132436 KB Output is correct
58 Correct 263 ms 119476 KB Output is correct
59 Correct 249 ms 119380 KB Output is correct
60 Correct 253 ms 113324 KB Output is correct
61 Correct 451 ms 206432 KB Output is correct
62 Correct 447 ms 176636 KB Output is correct
63 Correct 400 ms 89684 KB Output is correct
64 Correct 387 ms 69204 KB Output is correct
65 Correct 319 ms 55892 KB Output is correct
66 Correct 303 ms 48980 KB Output is correct
67 Correct 314 ms 45080 KB Output is correct
68 Correct 277 ms 43860 KB Output is correct
69 Correct 269 ms 43348 KB Output is correct
70 Correct 292 ms 42876 KB Output is correct
71 Correct 278 ms 42692 KB Output is correct
72 Correct 276 ms 43092 KB Output is correct
73 Correct 286 ms 43832 KB Output is correct
74 Correct 289 ms 44004 KB Output is correct
75 Correct 265 ms 46032 KB Output is correct
76 Correct 312 ms 49068 KB Output is correct
77 Correct 290 ms 58312 KB Output is correct
78 Correct 158 ms 74172 KB Output is correct