제출 #39015

#제출 시각아이디문제언어결과실행 시간메모리
39015Aidyn_AHard route (IZhO17_road)C++14
19 / 100
2000 ms172472 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...