| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 39073 | 2018-01-09T07:16:09 Z | Aidyn_A | Hard route (IZhO17_road) | C++14 | 0 ms | 100416 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;
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
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 100416 KB | Output is correct |
| 2 | Incorrect | 0 ms | 100416 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 100416 KB | Output is correct |
| 2 | Incorrect | 0 ms | 100416 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 100416 KB | Output is correct |
| 2 | Incorrect | 0 ms | 100416 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |