답안 #759826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
759826	2023-06-16T21:50:31 Z	NK_	Hard route (IZhO17_road)	C++17	0 / 100	1 ms	340 KB

road

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second
#define mp make_pair

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

using pi = pair<int, int>;
using ll = long long;

template<class T> using V = vector<T>;
template<class T> using mset = multiset<T>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;

	V<V<int>> adj(N);
	V<int> deg(N);

	int T = 0;
	for(int i = 0; i < N-1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
		deg[u]++, deg[v]++;
	}	

	int R = -1; for(int i = N-1; i >= 0; i--) {
		if (deg[i] > 1) R = i;
		else T++;
	}

	if (R == -1) {
		cout << 0 << " " << 1 << nl;
		return 0;
	}


	ll ans = 0, ways = T * (T - 1) / 2;
	V<pi> dp(N); V<map<int, int>> chd(N); 
	function<void(int, int)> gen = [&](int u, int p) {
		for(auto v : adj[u]) if (v != p) {
			gen(v, u); chd[u][dp[v].f] += dp[v].s;
		};
		
		if (sz(chd[u])) { dp[u] = *rbegin(chd[u]); dp[u].f++; }
		else dp[u] = mp(0, 1);	
	};

	gen(R, -1);

	auto upd = [&](int u, int k, int v) {
		chd[u][k] += v;
		if (chd[u][k] == 0) chd[u].erase(k);

		if (sz(chd[u])) { dp[u] = *rbegin(chd[u]); dp[u].f++; }
		else dp[u] = mp(0, 1);	
	};	

	function<void(int, int)> dfs = [&](int u, int p) {
		// cout << "NODE: " << u << " " << p << endl;
		V<pi> chd = {};
		for(auto v : adj[u]) chd.pb(dp[v]);

		sort(rbegin(chd), rend(chd));


		// if (p != -1 && size(chd) >= 2) {
		// 	// C is from above
		// 	int a = chd[0].f, b = chd[1].f;
		// 	ll R = 0;
		// 	if (a == b) {
		// 		ll sum = 0; for(auto x : chd) if (x.f == a) sum += x.s;
		// 		for(auto x : chd) R += (sum -= x.s) * x.s;
		// 	} else {
		// 		ll sum = 0; for(auto x : chd) if (x.f == b) sum += x.s;
		// 		R += sum * 1LL * chd[0].s;
		// 	}

		// 	int c = dp[p].f;

		// 	ll H = c * (a + b);
		// }

		// // All 3 are children
		// if (size(chd) >= 3) {
		// 	int a = chd[0].f, b = chd[1].f, c = chd[2].f;	

		// 	if (a == b && b == c) {
		// 		ll sum = 0, cnt = 0; for(auto x : chd) if (x.f == a) sum += x.s, cnt++;
		// 		for(auto x : chd) R += (sum -= x.s) * x.s * (cnt - 2);
		// 	}


		// }


		if (size(chd) >= 3) {
			int a, at; tie(a, at) = chd[0];
			int b, bt; tie(b, bt) = chd[1];
			int c, ct; tie(c, ct) = chd[2];

			ll R = 0;
			if (a == b && b == c) {
				ll sum = 0, cnt = 0; for(auto x : chd) if (x.f == a) sum += x.s, cnt++;
				for(auto x : chd) if (x.f == a) R += (sum -= x.s) * 1LL * x.s * 1LL * (cnt - 2);
			}

			if (a != b && b == c) {
				ll sum = 0, cnt = 0; for(auto x : chd) if (x.f == b) sum += x.s, cnt++;
				// cout << sum << " - " << cnt << nl;
				for(auto x : chd) if (x.f == b) R += (sum -= x.s) * 1LL * x.s;
			}

			if (a == b && b != c) {
				ll sum = 0, cnt = 0; for(auto x : chd) if (x.f == c) sum += x.s, cnt++;
				R += sum * 1LL * (at + bt);
			}

			if (a != b && b != c) {
				R += bt * 1LL * ct;
			}

			++a, ++b, ++c;

			// cout << a << " - " << b << " - " << c << endl;
			// cout << at << " - " << bt << " - " << ct << endl;

			ll H = (c + b) * 1LL * a;
			// cout << "(H, R) -> (" << H << ", " << R << ") " << endl;

			if (ans < H) ans = H, ways = 0;
			if (ans == H) ways += R;
		}

		for(auto v : adj[u]) if (v != p) {
			upd(u, dp[v].f, -dp[v].s);
			upd(v, dp[u].f, dp[u].s);

			dfs(v, u);

			upd(v, dp[u].f, -dp[u].s);
			upd(u, dp[v].f, dp[v].s);
		}
	};

	dfs(R, -1);

	cout << ans << " " << ways << nl;

    return 0;
}

Subtask #1

0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	316 KB	Output is correct
7	Correct	1 ms	324 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	320 KB	Output is correct
16	Correct	1 ms	320 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	320 KB	Output is correct
21	Incorrect	1 ms	312 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #2

0 / 33.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	316 KB	Output is correct
7	Correct	1 ms	324 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	320 KB	Output is correct
16	Correct	1 ms	320 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	320 KB	Output is correct
21	Incorrect	1 ms	312 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3

0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	324 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	316 KB	Output is correct
7	Correct	1 ms	324 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	320 KB	Output is correct
16	Correct	1 ms	320 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	320 KB	Output is correct
21	Incorrect	1 ms	312 KB	Output isn't correct
22	Halted	0 ms	0 KB	-