oj.uz

답안 #39015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39015 2018-01-09T05:18:01 Z Aidyn_A Hard route (IZhO17_road) C++14
19 / 100
 2000 ms 172472 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 <= 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.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 172156 KB Output is correct
2 Correct 0 ms 172156 KB Output is correct
3 Correct 3 ms 172156 KB Output is correct
4 Correct 3 ms 172156 KB Output is correct
5 Correct 3 ms 172156 KB Output is correct
6 Correct 0 ms 172156 KB Output is correct
7 Correct 3 ms 172156 KB Output is correct
8 Correct 6 ms 172156 KB Output is correct
9 Correct 6 ms 172156 KB Output is correct
10 Correct 6 ms 172156 KB Output is correct
11 Correct 3 ms 172156 KB Output is correct
12 Correct 0 ms 172156 KB Output is correct
13 Correct 3 ms 172156 KB Output is correct
14 Correct 3 ms 172156 KB Output is correct
15 Correct 0 ms 172156 KB Output is correct
16 Correct 9 ms 172156 KB Output is correct
17 Correct 0 ms 172156 KB Output is correct
18 Correct 0 ms 172156 KB Output is correct
19 Correct 0 ms 172156 KB Output is correct
20 Correct 6 ms 172156 KB Output is correct
21 Correct 6 ms 172156 KB Output is correct
22 Correct 0 ms 172156 KB Output is correct
23 Correct 0 ms 172156 KB Output is correct
24 Correct 3 ms 172156 KB Output is correct

Subtask #2
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 172156 KB Output is correct
2 Correct 0 ms 172156 KB Output is correct
3 Correct 3 ms 172156 KB Output is correct
4 Correct 3 ms 172156 KB Output is correct
5 Correct 3 ms 172156 KB Output is correct
6 Correct 0 ms 172156 KB Output is correct
7 Correct 3 ms 172156 KB Output is correct
8 Correct 6 ms 172156 KB Output is correct
9 Correct 6 ms 172156 KB Output is correct
10 Correct 6 ms 172156 KB Output is correct
11 Correct 3 ms 172156 KB Output is correct
12 Correct 0 ms 172156 KB Output is correct
13 Correct 3 ms 172156 KB Output is correct
14 Correct 3 ms 172156 KB Output is correct
15 Correct 0 ms 172156 KB Output is correct
16 Correct 9 ms 172156 KB Output is correct
17 Correct 0 ms 172156 KB Output is correct
18 Correct 0 ms 172156 KB Output is correct
19 Correct 0 ms 172156 KB Output is correct
20 Correct 6 ms 172156 KB Output is correct
21 Correct 6 ms 172156 KB Output is correct
22 Correct 0 ms 172156 KB Output is correct
23 Correct 0 ms 172156 KB Output is correct
24 Correct 3 ms 172156 KB Output is correct
25 Correct 686 ms 172288 KB Output is correct
26 Correct 606 ms 172300 KB Output is correct
27 Correct 786 ms 172288 KB Output is correct
28 Correct 429 ms 172320 KB Output is correct
29 Correct 1669 ms 172420 KB Output is correct
30 Correct 1929 ms 172428 KB Output is correct
31 Correct 1869 ms 172428 KB Output is correct
32 Correct 1739 ms 172420 KB Output is correct
33 Correct 13 ms 172296 KB Output is correct
34 Correct 9 ms 172328 KB Output is correct
35 Correct 9 ms 172320 KB Output is correct
36 Correct 9 ms 172300 KB Output is correct
37 Correct 9 ms 172344 KB Output is correct
38 Correct 13 ms 172472 KB Output is correct
39 Correct 6 ms 172288 KB Output is correct
40 Correct 9 ms 172288 KB Output is correct
41 Correct 9 ms 172288 KB Output is correct
42 Correct 6 ms 172288 KB Output is correct
43 Correct 16 ms 172288 KB Output is correct
44 Correct 19 ms 172288 KB Output is correct
45 Correct 76 ms 172288 KB Output is correct
46 Correct 216 ms 172288 KB Output is correct
47 Correct 1136 ms 172432 KB Output is correct
48 Execution timed out 2000 ms 172420 KB Execution timed out

Subtask #3
0 / 48.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 172156 KB Output is correct
2 Correct 0 ms 172156 KB Output is correct
3 Correct 3 ms 172156 KB Output is correct
4 Correct 3 ms 172156 KB Output is correct
5 Correct 3 ms 172156 KB Output is correct
6 Correct 0 ms 172156 KB Output is correct
7 Correct 3 ms 172156 KB Output is correct
8 Correct 6 ms 172156 KB Output is correct
9 Correct 6 ms 172156 KB Output is correct
10 Correct 6 ms 172156 KB Output is correct
11 Correct 3 ms 172156 KB Output is correct
12 Correct 0 ms 172156 KB Output is correct
13 Correct 3 ms 172156 KB Output is correct
14 Correct 3 ms 172156 KB Output is correct
15 Correct 0 ms 172156 KB Output is correct
16 Correct 9 ms 172156 KB Output is correct
17 Correct 0 ms 172156 KB Output is correct
18 Correct 0 ms 172156 KB Output is correct
19 Correct 0 ms 172156 KB Output is correct
20 Correct 6 ms 172156 KB Output is correct
21 Correct 6 ms 172156 KB Output is correct
22 Correct 0 ms 172156 KB Output is correct
23 Correct 0 ms 172156 KB Output is correct
24 Correct 3 ms 172156 KB Output is correct
25 Correct 686 ms 172288 KB Output is correct
26 Correct 606 ms 172300 KB Output is correct
27 Correct 786 ms 172288 KB Output is correct
28 Correct 429 ms 172320 KB Output is correct
29 Correct 1669 ms 172420 KB Output is correct
30 Correct 1929 ms 172428 KB Output is correct
31 Correct 1869 ms 172428 KB Output is correct
32 Correct 1739 ms 172420 KB Output is correct
33 Correct 13 ms 172296 KB Output is correct
34 Correct 9 ms 172328 KB Output is correct
35 Correct 9 ms 172320 KB Output is correct
36 Correct 9 ms 172300 KB Output is correct
37 Correct 9 ms 172344 KB Output is correct
38 Correct 13 ms 172472 KB Output is correct
39 Correct 6 ms 172288 KB Output is correct
40 Correct 9 ms 172288 KB Output is correct
41 Correct 9 ms 172288 KB Output is correct
42 Correct 6 ms 172288 KB Output is correct
43 Correct 16 ms 172288 KB Output is correct
44 Correct 19 ms 172288 KB Output is correct
45 Correct 76 ms 172288 KB Output is correct
46 Correct 216 ms 172288 KB Output is correct
47 Correct 1136 ms 172432 KB Output is correct
48 Execution timed out 2000 ms 172420 KB Execution timed out