제출 #1269188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269188		g4yuhg	Hard route (IZhO17_road)	C++20	100 / 100	608 ms	160388 KiB

road

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define pii pair<ll, ll>
#define MP make_pair
#define fi first
#define se second
#define TASK "road"
#define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);
#define N 500005
#define LOG 19
#define endl '\n'
using namespace std;

bool ghuy4g;

ll n;
vector<ll> adj[N];

ll d[N][2], c[N][2];

pii ans;

void dfs(ll u, ll parent) {
	vector<pii> vt;
	for (auto v : adj[u]) {
		if (v == parent) continue;
		dfs(v, u);
		//vt.push_back({d[v][0] + 1, c[v][0]});
		d[v][0] ++ ;
		if (d[v][0] >= d[u][0]) {
			d[u][1] = d[u][0];
			d[u][0] = d[v][0];
		}
		else if (d[v][0] >= d[u][1]) {
			d[u][1] = d[v][0];
		}
		d[v][0] -- ;
	}
	for (auto v : adj[u]) {
		if (v == parent) continue;
		if (d[v][0] + 1 == d[u][0]) {
			c[u][0] += c[v][0];
		}
		if (d[v][0] + 1 == d[u][1]) {
			c[u][1] += c[v][0];
		}
	}
	if (d[u][0] == 0) {
		c[u][0] = 1;
	}
	if (d[u][1] == 0) {
		c[u][1] = 1;
	}
}

void reroot(ll u, ll parent) {
	d[u][0] = d[u][1] = c[u][0] = c[u][1] = 0;
	vector<pii> vt;
	for (auto v : adj[u]) {
		vt.push_back({d[v][0] + 1, c[v][0]});
		d[v][0] ++ ;
		if (d[v][0] >= d[u][0]) {
			d[u][1] = d[u][0];
			d[u][0] = d[v][0];
		}
		else if (d[v][0] >= d[u][1]) {
			d[u][1] = d[v][0];
		}
		d[v][0] -- ;
		if (u == 2) {
			//cout << v << " : " << d[v][0] + 1 << " " << c[v][0] << endl;
		}
	}
	for (auto v : adj[u]) {
		if (d[v][0] + 1 == d[u][0]) {
			c[u][0] += c[v][0];
		}
		if (d[v][0] + 1 == d[u][1]) {
			c[u][1] += c[v][0];
		}
	}
	if (d[u][0] == 0) {
		c[u][0] = 1;
	}
	if (d[u][1] == 0) {
		c[u][1] = 1;
	}
	pii cnt = {0, 0}; // cnt.fi la ket qua, cnt.se la so con dai bang con thu 2
	if (adj[u].size() >= 3) {
		sort(vt.begin(), vt.end(), greater<pii>());
		ll x = vt[0].fi * (vt[1].fi + vt[2].fi);
		for (pii it : vt) { 
			// ta dang thu chon con it nay la con thu 2
			// => no se gop voi cac con bang con thu nhat dang truoc
			// 0 = 1 = 2 van duoc, vi luon luon co 1 con lam nhanh dai nhat
			if (it.fi == vt[2].fi) {
				cnt.fi += cnt.se * it.se;
			}
			if (it.fi == vt[1].fi) {
				cnt.se += it.se;
			}
		}
		if (x > ans.fi) {
			ans.fi = x;
			ans.se = cnt.fi;
		}
		else if (x == ans.fi) {
			ans.se += cnt.fi;
		}
	}
	for (auto v : adj[u]) {
		if (v == parent) continue;
		ll dv0 = d[v][0], cv0 = c[v][0], du0 = d[u][0], cu0 = c[u][0], dv1 = d[v][1], cv1 = c[v][1];
		if (d[v][0] + 1 == d[u][0]) {
			if (c[v][0] == c[u][0]) { // nhanh to nhat la nhanh nay luon, khong co thu 2
				d[u][0] = d[u][1];
				c[u][0] = c[u][1];
			}
			else {
				if (u == 1 && v == 2) {
					//cout << c[u][0] << " " << c[v][0] << endl;
				}
				c[u][0] -= c[v][0];
			}
		}
		if (u == 2 && v == 3) {
			//cout << d[u][0] << " here " << endl;
		}
		reroot(v, u);
		d[v][0] = dv0, c[v][0] = cv0, d[u][0] = du0, c[u][0] = cu0, d[v][1] = dv1, c[v][1] = cv1;
	}
}

bool klinh;

signed main(void) {
	start;
    faster;
    
	cin >> n;
	for (int i = 1; i <= n - 1; i ++) {
		ll u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	ll r = 1;
	dfs(r, r);
	reroot(r, r);
	
	if (ans.fi == 0) ans.se = 1;
	
	cout << ans.fi << " " << ans.se;
   	
    cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

road.cpp: In function 'int main()':
road.cpp:9:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
road.cpp:139:9: note: in expansion of macro 'start'
  139 |         start;
      |         ^~~~~
road.cpp:9:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define start if(fopen(TASK".in","r")){freopen(TASK".in","r",stdin);freopen(TASK".out","w",stdout);}
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
road.cpp:139:9: note: in expansion of macro 'start'
  139 |         start;
      |         ^~~~~

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