Submission #1219393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219393		hoa208	Hard route (IZhO17_road)	C++20	19 / 100	7 ms	12872 KiB

road

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define pa pair<ll, ll>
#define fi first
#define se second
#define bit(mask, j) ((mask >> j) & 1)
#define t_test int t;cin >> t;while(t--)
const   ll mod = 1e9 + 7;
const   ll INF = 1e18;
inline  void adm(ll &x){if(x>=mod)x%=mod;else if(x<0)x+=mod;}
//--------------------------------------------------------------------
const ll N = 5e5 + 10;
ll n;
pa ans;
vector<ll> g[N];
struct DP {
	ll cur, cnt;
	bool operator < (const DP &a) {
		return cur > a.cur;
	}
} dp[N], rdp[N];
void dfs1(ll u, ll p) {
	dp[u].cnt = 1;
	for(auto v : g[u]) {
		if(v == p) continue;
		dfs1(v, u);
		if(dp[u].cur == dp[v].cur + 1) {
			dp[u].cnt += dp[v].cnt;
		}
		else if(dp[u].cur < dp[v].cur + 1) {
			dp[u].cur = dp[v].cur + 1;
			dp[u].cnt = dp[v].cnt;
		}
	}
}
void dfs2(ll u, ll p) {
	vector<DP> vt;
	if(u != 1 || g[u].size() == 1) {
		vt.push_back({rdp[u].cur, rdp[u].cnt});
	}
	for(auto v : g[u]) {
		if(v == p) continue;
		vt.push_back({dp[v].cur + 1, dp[v].cnt});
	}
	sort(vt.begin(), vt.end());
	if(vt.size() >= 3) {
		ll socach = 0;
		DP A = vt[0], B = vt[1], C = vt[2];
		ll res = A.cur * (B.cur + C.cur);
		if(A.cur == B.cur && B.cur == C.cur) {
			ll res = A.cnt + B.cnt + C.cnt;
			ll cnt = 0;
			for(auto e : vt) {
				if(e.cur == A.cur) cnt += e.cnt;
			}
			for(auto e : vt) {
				if(e.cur == A.cur) {
					cnt -= e.cnt;
					socach = socach + e.cnt * cnt; 
				}
			}
		}
		else if(A.cur != B.cur && B.cur != C.cur) {
			ll cnt = 0;
			for(auto e : vt) {
				if(e.cur == C.cur) cnt++;
			}
			socach = B.cnt * cnt;
		}
		else if(A.cur == B.cur) {
			ll cnt = 0;
			for(auto e : vt) {
				if(e.cur == C.cur) cnt++;
			}
			socach = (B.cnt + A.cnt) * cnt;
		}
		else {
			ll cnt = 0;
			for(auto e : vt) {
				if(e.cur == C.cur) cnt += e.cnt;
			}
			
			for(auto e : vt) {
				if(e.cur == C.cur) {
					cnt -= e.cnt;
					socach = socach + cnt * e.cnt;
				}
			}
		}
		if(res > ans.fi) {
			ans.fi = res;
			ans.se = socach;
		}
		else if(res == ans.fi) {
			ans.se += socach;
		}
	}
	ll max1 = -1, max2 = -1, cnt1 = 0, cnt2 = 0;
	for(auto e : vt) {
		if(max1 == -1 || e.cur + 1 == max1) {
			max1 = e.cur + 1;
			cnt1 += e.cnt;
		}
		else if(max2 == -1 || e.cur + 1 == max2) {
			max2 = e.cur + 1;
			cnt2 += e.cnt;
		}
	}
	vt.clear();
	for(auto v : g[u]) {
		if(v == p) continue;
		if(max1 == dp[v].cur + 2) {
			if(cnt1 == dp[v].cnt) {
				rdp[v] = {max2, cnt2};
			}
			else rdp[v] = {max1, cnt1 - dp[v].cnt};
		}
		else rdp[v] = {max1, cnt1};
		dfs2(v, u);
	}
}
void hbmt() {
	cin >> n;
	FOR(i, 1, n - 1) {
		ll u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	ans.se = 1;
	rdp[1].cnt = 1;
	dfs1(1, 0);
	dfs2(1, 0);
	cout << ans.fi << ' ' << ans.se;
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	
	if(fopen("hbmt.inp", "r")) {
		freopen("hbmt.inp", "r", stdin);
		freopen("hbmt.out", "w", stdout);
	}
	
	// t_test 
	hbmt();
	return 0;
}

Compilation message (stderr)

road.cpp: In function 'int main()':
road.cpp:146:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |                 freopen("hbmt.inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
road.cpp:147:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |                 freopen("hbmt.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 33
• Subtask 3: 0 / 48