oj.uz

Submission #39019

# Submission time Handle Problem Language Result Execution time Memory
39019 2018-01-09T05:31:35 Z Aidyn_A Hard route (IZhO17_road) C++14
19 / 100
 2000 ms 172492 KB 
#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 <= 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);
	}
}

int bar[5005][5005], 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], 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) {
			pos[i] = sz(leaf);
			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 --;
 			}
 			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;
			/*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;         
}

Compilation message

road.cpp: In function 'int main()':
road.cpp:145:37: warning: unused variable 'r' [-Wunused-variable]
   int prv = -1, cur = 0, l = i - 1, r = i + 1, temp = 0, what = 0;
                                     ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 172172 KB Output is correct
2 Correct 3 ms 172172 KB Output is correct
3 Correct 6 ms 172172 KB Output is correct
4 Correct 0 ms 172172 KB Output is correct
5 Correct 0 ms 172172 KB Output is correct
6 Correct 0 ms 172172 KB Output is correct
7 Correct 6 ms 172172 KB Output is correct
8 Correct 0 ms 172172 KB Output is correct
9 Correct 9 ms 172172 KB Output is correct
10 Correct 0 ms 172172 KB Output is correct
11 Correct 6 ms 172172 KB Output is correct
12 Correct 3 ms 172172 KB Output is correct
13 Correct 3 ms 172172 KB Output is correct
14 Correct 0 ms 172172 KB Output is correct
15 Correct 3 ms 172172 KB Output is correct
16 Correct 6 ms 172172 KB Output is correct
17 Correct 3 ms 172172 KB Output is correct
18 Correct 0 ms 172172 KB Output is correct
19 Correct 0 ms 172172 KB Output is correct
20 Correct 3 ms 172172 KB Output is correct
21 Correct 6 ms 172172 KB Output is correct
22 Correct 3 ms 172172 KB Output is correct
23 Correct 9 ms 172172 KB Output is correct
24 Correct 0 ms 172172 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 172172 KB Output is correct
2 Correct 3 ms 172172 KB Output is correct
3 Correct 6 ms 172172 KB Output is correct
4 Correct 0 ms 172172 KB Output is correct
5 Correct 0 ms 172172 KB Output is correct
6 Correct 0 ms 172172 KB Output is correct
7 Correct 6 ms 172172 KB Output is correct
8 Correct 0 ms 172172 KB Output is correct
9 Correct 9 ms 172172 KB Output is correct
10 Correct 0 ms 172172 KB Output is correct
11 Correct 6 ms 172172 KB Output is correct
12 Correct 3 ms 172172 KB Output is correct
13 Correct 3 ms 172172 KB Output is correct
14 Correct 0 ms 172172 KB Output is correct
15 Correct 3 ms 172172 KB Output is correct
16 Correct 6 ms 172172 KB Output is correct
17 Correct 3 ms 172172 KB Output is correct
18 Correct 0 ms 172172 KB Output is correct
19 Correct 0 ms 172172 KB Output is correct
20 Correct 3 ms 172172 KB Output is correct
21 Correct 6 ms 172172 KB Output is correct
22 Correct 3 ms 172172 KB Output is correct
23 Correct 9 ms 172172 KB Output is correct
24 Correct 0 ms 172172 KB Output is correct
25 Correct 383 ms 172304 KB Output is correct
26 Correct 333 ms 172312 KB Output is correct
27 Correct 393 ms 172304 KB Output is correct
28 Correct 203 ms 172340 KB Output is correct
29 Correct 1219 ms 172436 KB Output is correct
30 Correct 1046 ms 172452 KB Output is correct
31 Correct 1053 ms 172448 KB Output is correct
32 Correct 1002 ms 172436 KB Output is correct
33 Correct 16 ms 172312 KB Output is correct
34 Correct 9 ms 172344 KB Output is correct
35 Correct 13 ms 172336 KB Output is correct
36 Correct 9 ms 172324 KB Output is correct
37 Correct 6 ms 172364 KB Output is correct
38 Correct 6 ms 172492 KB Output is correct
39 Correct 13 ms 172304 KB Output is correct
40 Correct 6 ms 172304 KB Output is correct
41 Correct 13 ms 172304 KB Output is correct
42 Correct 9 ms 172304 KB Output is correct
43 Correct 6 ms 172304 KB Output is correct
44 Correct 13 ms 172304 KB Output is correct
45 Correct 49 ms 172304 KB Output is correct
46 Correct 99 ms 172304 KB Output is correct
47 Correct 603 ms 172448 KB Output is correct
48 Execution timed out 2000 ms 172436 KB Execution timed out

Subtask #3
0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 172172 KB Output is correct
2 Correct 3 ms 172172 KB Output is correct
3 Correct 6 ms 172172 KB Output is correct
4 Correct 0 ms 172172 KB Output is correct
5 Correct 0 ms 172172 KB Output is correct
6 Correct 0 ms 172172 KB Output is correct
7 Correct 6 ms 172172 KB Output is correct
8 Correct 0 ms 172172 KB Output is correct
9 Correct 9 ms 172172 KB Output is correct
10 Correct 0 ms 172172 KB Output is correct
11 Correct 6 ms 172172 KB Output is correct
12 Correct 3 ms 172172 KB Output is correct
13 Correct 3 ms 172172 KB Output is correct
14 Correct 0 ms 172172 KB Output is correct
15 Correct 3 ms 172172 KB Output is correct
16 Correct 6 ms 172172 KB Output is correct
17 Correct 3 ms 172172 KB Output is correct
18 Correct 0 ms 172172 KB Output is correct
19 Correct 0 ms 172172 KB Output is correct
20 Correct 3 ms 172172 KB Output is correct
21 Correct 6 ms 172172 KB Output is correct
22 Correct 3 ms 172172 KB Output is correct
23 Correct 9 ms 172172 KB Output is correct
24 Correct 0 ms 172172 KB Output is correct
25 Correct 383 ms 172304 KB Output is correct
26 Correct 333 ms 172312 KB Output is correct
27 Correct 393 ms 172304 KB Output is correct
28 Correct 203 ms 172340 KB Output is correct
29 Correct 1219 ms 172436 KB Output is correct
30 Correct 1046 ms 172452 KB Output is correct
31 Correct 1053 ms 172448 KB Output is correct
32 Correct 1002 ms 172436 KB Output is correct
33 Correct 16 ms 172312 KB Output is correct
34 Correct 9 ms 172344 KB Output is correct
35 Correct 13 ms 172336 KB Output is correct
36 Correct 9 ms 172324 KB Output is correct
37 Correct 6 ms 172364 KB Output is correct
38 Correct 6 ms 172492 KB Output is correct
39 Correct 13 ms 172304 KB Output is correct
40 Correct 6 ms 172304 KB Output is correct
41 Correct 13 ms 172304 KB Output is correct
42 Correct 9 ms 172304 KB Output is correct
43 Correct 6 ms 172304 KB Output is correct
44 Correct 13 ms 172304 KB Output is correct
45 Correct 49 ms 172304 KB Output is correct
46 Correct 99 ms 172304 KB Output is correct
47 Correct 603 ms 172448 KB Output is correct
48 Execution timed out 2000 ms 172436 KB Execution timed out