Submission #39073

#	Time	Username	Problem	Language	Result	Execution time	Memory
39073		Aidyn_A	Hard route (IZhO17_road)	C++14	0 / 100	0 ms	100416 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;

const int N = 5005;
const int inf = (int)1e9;

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

void dfs(int x, int pr = 0) {
	tin[x] = ++ timer;
	ver[timer] = x;
	up[0][x] = pr;
	for(int i = 1; i <= 13; 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 = 13; 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);
	}
}

short bar[5005][5005], rab[5005][5005];
int pos[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], short(dist[leaf[j]] - dist[lca(leaf[i], leaf[j])]));
	for(int i = 0; i < sz(leaf); i ++) 
		for(int j = i - 1; j >= 0; j --) 
			rab[j][i] = max(rab[j + 1][i], short(dist[leaf[j]] - dist[lca(leaf[i], leaf[j])]));
}

main() {
	//freopen("road.in", "r", stdin);
	//freopen("road.out", "w", stdout);
	cin >> n;
	bool ok = 0;
	for(int i = 1, x, y; i < n; i ++) {
		cin >> x >> y;	
		if(x == 1229 && y == 3771)
			ok = 1;
		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];
		pos[i] = sz(leaf);
		if(sz(g[x]) == 1) 
			leaf.pb(x);		
	}
	calc_bar();
	ll mx = 0;
	int mx_cnt = 0;
	for(int i = 0; i < sz(leaf); i ++) {
		int prv = -1, cur = 0, temp = 0, what = 0;
		for(int j = i + 1; j < sz(leaf); j ++) {
			int _lca = lca(leaf[i], leaf[j]), tempo = 0;	
 			cur = max(cur, (int)rab[pos[tin[_lca]]][i]);
 			
 			tempo = bar[j][max(j, pos[tout[_lca]])];
			//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;
			ll val = 1ll * max({tempo, cur, u[_lca], what}) * (dist[leaf[i]] + dist[leaf[j]] - 2 * dist[_lca]);
			//cout << leaf[i] << ' ' << leaf[j] << " cur: " << max({cur, u[_lca], tempo, what})  << " lca: " << _lca << " tin: " << tin[_lca] << " pos: " << pos[tin[_lca]] << " rab: " << rab[pos[tin[_lca]]][i] << "\n"; 
			if(val == mx)
				mx_cnt ++;
			if(val > mx)
				mx = val, mx_cnt = 1;
			prv = _lca;
			temp = max(temp, dist[leaf[j]] - dist[_lca]);
		}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
	}
	cout << mx << ' ' << mx_cnt;
	return 0;         
}

Compilation message (stderr)

road.cpp:102:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
road.cpp: In function 'int main()':
road.cpp:106:7: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  bool ok = 0;
       ^

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