| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 39015 |
2018-01-09T05:18:01 Z |
Aidyn_A |
Hard route (IZhO17_road) |
C++14 |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
