제출 #39015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39015		Aidyn_A	Hard route (IZhO17_road)	C++14	19 / 100	2000 ms	172472 KiB

road

#include <stdio.h>
#include <bits/stdc++.h>			

#define pb push_back
#define pf push_front
#define pp pop_back
#define sz(a) (int)(a.size())
#define mp make_pair
#define F first
#define S second
#define next _next
#define prev _prev
#define left _left
#define right _right
#define y1 _y1
#define all(x) x.begin(), x.end()
#define what_is(x) #x << " is " << (x)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = (int)5e5 + 123;
const ll INF = (ll)1e18 + 123;
const int inf = (int)1e9 + 123;
const int MOD = (int)1e9 + 7;

void megaRandom() {
	unsigned int FOR;
 	asm("rdtsc" : "=A"(FOR));
  srand(FOR);
}

int n;
vector<int> g[N];
int down[N], u[N];
int up[25][N], tin[N], tout[N], timer;
int dist[N], ver[N];

void dfs(int x, int pr = 0) {
	tin[x] = ++ timer;
	ver[timer] = x;
	up[0][x] = pr;
	for(int i = 1; i <= 20; i ++)
		up[i][x] = up[i - 1][up[i - 1][x]];		
	for(auto to : g[x]) {
		if(to == pr)
			continue;
		dist[to] = dist[x] + 1;
		dfs(to, x);
		down[x] = max(down[x], down[to] + 1);	
	}
	tout[x] = timer;
}

bool is_par(int x, int y) {
	return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}

int lca(int x, int y) {
	if(is_par(x, y)) return x;
	if(is_par(y, x)) return y;
	int v = x;
	for(int i = 20; i >= 0; i --) 
		if(up[i][v] > 0 && !is_par(up[i][v], y))
			v = up[i][v];
  return up[0][v]; 	
}

void calc_u(int x, int pr = 0) {
	int mx1 = -inf, mx2 = -inf;
	for(auto to : g[x]) {
		if(to == pr)
			continue;
		if(down[to] > mx1)
			mx2 = mx1, mx1 = down[to];			
		else 
			mx2 = max(mx2, down[to]);
	}
	for(auto to : g[x]) {
		if(to == pr) 
			continue;
		u[to] = max(u[to], u[x] + 1);
		if(mx1 == down[to])
			u[to] = max(u[to], mx2 + 2);
		else
			u[to] = max(u[to], mx1 + 2);
	}
	for(auto to : g[x]) {
		if(to == pr)
			continue;
		calc_u(to, x);
	}
}

int bar[5005][5005];
vector<int> leaf;

void calc_bar() {
	for(int i = 0; i < sz(leaf); i ++) 
		for(int j = i + 1; j < sz(leaf); j ++) 
			bar[i][j] = max(bar[i][j - 1], dist[leaf[j]] - dist[lca(leaf[i], leaf[j])]);
}

int main() {
	megaRandom();
	//freopen("road.in", "r", stdin);
	//freopen("road.out", "w", stdout);
	cin >> n;
	for(int i = 1, x, y; i < n; i ++) {
		cin >> x >> y;	
		g[x].pb(y), g[y].pb(x);
	}
	if(n == 2) {
		cout << "0 1";
		return 0;		
	}
	int start = 1;
	for(int i = 1; i <= n; i ++) {
		if(sz(g[i]) != 1) {
			start = i;
			break;
		}
	}
	dfs(start);
	calc_u(start);
	//cout << "start: " << start << "\n";

	for(int i = 1; i <= n; i ++) {
		//cout << "i: " << i << " up: " << u[i] << "\n";
		int x = ver[i];
		if(sz(g[x]) == 1)
			leaf.pb(x);		
	}
	calc_bar();
	int mx = 0, mx_cnt = 0;
	for(int i = 0; i < sz(leaf); i ++) {
		int prv = -1, cur = 0, l = i - 1, r = i + 1, temp = 0, what = 0;
		for(int j = i + 1; j < sz(leaf); j ++) {
			int _lca = lca(leaf[i], leaf[j]), tempo = 0;	
 			while(l >= 0 && is_par(_lca, lca(leaf[l], leaf[i]))) {
 				cur = max(cur, dist[leaf[l]] - dist[lca(leaf[l], leaf[i])]);
 				l --;
 			}
 			while(r < sz(leaf) && is_par(_lca, lca(leaf[j], leaf[r])))
 				r ++;
 			tempo = bar[j][max(j, r - 1)];
			if(prv == _lca) 
				what = max(what, dist[leaf[j - 1]] - dist[lca(leaf[j - 1], leaf[j])]);
			if(prv != -1 && prv != _lca)
				cur = max(cur, temp), what = 0;
			/*if(1872 ==  (dist[leaf[i]] + dist[leaf[j]] - 2 * dist[_lca]) * temp && n == 100) {
				cout << "temp!\n" << temp;
				return 0;
			}
			if(1872 == tempo * (dist[leaf[i]] + dist[leaf[j]] - 2 * dist[_lca]) && n == 100) {
				cout << "tempo!\n" << tempo;
				return 0;
			}
			if(1872 == u[_lca] * (dist[leaf[i]] + dist[leaf[j]] - 2 * dist[_lca]) && n == 100) {
				cout << "u[_lca]!\n" << u[_lca];
				return 0;
			}
			if(1872 == what * (dist[leaf[i]] + dist[leaf[j]] - 2 * dist[_lca]) && n == 100) {
				cout << "what!\n" << what;
				return 0;
			} */
			//cout << leaf[i] << ' ' << leaf[j] << " cur: " << max({cur, u[_lca], tempo, what}) << " bar: " << bar[j][r - 1] << " r: " << r << " lca: " << _lca << "\n"; 
			if(max({tempo, cur, u[_lca], what}) * (dist[leaf[i]] + dist[leaf[j]] - 2 * dist[_lca]) == mx)
				mx_cnt ++;
			if(max({tempo, cur, u[_lca], what}) * (dist[leaf[i]] + dist[leaf[j]] - 2 * dist[_lca]) > mx)
				mx = max({tempo, cur, u[_lca], what}) * (dist[leaf[i]] + dist[leaf[j]] - 2 * dist[_lca]), mx_cnt = 1;
			prv = _lca;
			temp = max(temp, dist[leaf[j]] - dist[_lca]);
		}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
	}
	cout << mx << ' ' << mx_cnt;
	return 0;         
}

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