| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 564305 |
2022-05-18T21:50:47 Z |
urosk |
Hard route (IZhO17_road) |
C++14 |
|
11 ms |
15956 KB |
// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 500005
ll n;
vector<ll> g[maxn];
ll d[maxn];
void naj(ll u,ll par){
d[u] = d[par] + 1;
for(ll s : g[u]){
if(s==par) continue;
naj(s,u);
}
}
ll naj(ll u){
fill(d,d+maxn,llinf);
d[u] = -1;
naj(u,u);
ll s = u;
for(ll i = 1;i<=n;i++){
if(d[i]>d[s]) s = i;
}
return s;
}
ll rut = 0;
vector<ll> v;
void froot(ll u,ll par,ll f){
if(u==f){
rut = v[sz(v)/2];
return;
}
v.pb(u);
for(ll s : g[u]){
if(s==par) continue;
froot(s,u,f);
}
v.popb();
}
ll up[maxn];
pll mx[maxn];
pll c[maxn];
pll mrg(pll a,pll b){
if(a.fi!=b.fi) return max(a,b);
return {a.fi,a.sc+b.sc};
}
void dfs(ll u,ll par){
d[u] = d[par] + 1;
mx[u] = {0,1};
for(ll s : g[u]){
if(s==par) continue;
dfs(s,u);
mx[u] = mrg(mx[u],{mx[s].fi+1,mx[s].sc});
}
}
pll ans = {0,0};
void dfs2(ll u,ll par){
pll p = {0,0};
for(ll s : g[u]){
if(s==par) continue;
ll x = mx[s].fi+2;
if(p.fi<x) p = {x,p.fi};
else if(p.sc<x) p = {p.fi,x};
}
c[u] = p;
p = c[par];
if(u!=par){
ll x = p.fi;
if(p.fi==mx[u].fi+1) x = p.sc;
up[u] = max(up[par]+1,x);
}
p = {0,0};
for(ll s : g[u]){
if(s==par) continue;
ll x = mx[s].fi+1;
if(x>p.fi) p = {x,p.fi};
else if(x>p.sc) p = {p.fi,x};
}
pll cnt = {0,0};
for(ll s : g[u]){
if(s==par) continue;
ll x = mx[s].fi + 1;
if(x==p.fi) cnt.fi+=mx[s].sc;
else if(x==p.sc) cnt.sc+=mx[s].sc;
}
if(u==rut){
ll r = 0;
pll h = {0,0};
for(ll s : g[u]){
ll x = mx[s].fi + 1;
if(x==p.fi) h.fi++;
if(x==p.sc) h.sc++;
if(x!=p.fi&&x!=p.sc){
r = max(r,x);
continue;
}
if(p.fi==p.sc){
if(cnt.fi>2&&x==p.fi) r = max(r,x-1);
}else{
if(x==p.fi&&cnt.fi>1) r = max(r,x-1);
else if(x==p.sc&&cnt.sc>1) r = max(r,x-1);
}
}
if(p.fi==p.sc){
if(h.fi>2) r = p.fi;
}else{
if(h.sc>1) r = p.fi;
if(h.fi>1) r = p.fi;
}
up[u] = r;
}
if(p.fi!=0&&p.sc!=0){
if(p.fi!=p.sc){
pll cur = {up[u]*(p.fi+p.sc),cnt.fi*cnt.sc};
//cerr<<"u: "<<u<< " "<<cur.fi<< " "<<p.fi<< " "<<p.sc<<" "<<cnt.fi<< " "<<cnt.sc<<endl;
//cerr<<cur.fi<< " "<<cur.sc<<endl;
ans = mrg(ans,cur);
}else{
pll cur = {up[u]*2*p.fi,0};
//cerr<<"u: "<<u<< " "<<cur.fi<< " "<<p.fi<< " "<<p.sc<<" "<<cnt.fi<< " "<<cnt.sc<<endl;
for(ll s : g[u]){
if(s==par) continue;
if(mx[s].fi+1==p.fi){
cur.sc+=(cnt.fi-mx[s].sc)*mx[s].sc;
}
}
cur.sc/=2;
//cerr<<cur.fi<< " "<<cur.sc<<endl;
ans = mrg(ans,cur);
}
}
for(ll s : g[u]){
if(s==par) continue;
dfs2(s,u);
}
}
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n;
for(ll i = 1;i<=n-1;i++){
ll x,y; cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
ll x = naj(1);
ll y = naj(x);
froot(x,x,y);
fill(d,d+n+1,0);
dfs(rut,rut);
dfs2(rut,rut);
/*
here;
cerr<<"rut: "<<rut<<endl;
for(ll i = 1;i<=n;i++) cerr<<mx[i].fi<< " "<<mx[i].sc<<endl;
ceri(up,1,n);
here;
*/
cout<<ans.fi<< " "<<ans.sc<<endl;
return 0;
}
/*
7
1 2
1 3
2 4
2 5
3 6
3 7
4
1 2
2 3
2 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15956 KB |
Output is correct |
| 2 |
Correct |
9 ms |
15956 KB |
Output is correct |
| 3 |
Correct |
9 ms |
15956 KB |
Output is correct |
| 4 |
Correct |
8 ms |
15956 KB |
Output is correct |
| 5 |
Correct |
8 ms |
15896 KB |
Output is correct |
| 6 |
Incorrect |
11 ms |
15956 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15956 KB |
Output is correct |
| 2 |
Correct |
9 ms |
15956 KB |
Output is correct |
| 3 |
Correct |
9 ms |
15956 KB |
Output is correct |
| 4 |
Correct |
8 ms |
15956 KB |
Output is correct |
| 5 |
Correct |
8 ms |
15896 KB |
Output is correct |
| 6 |
Incorrect |
11 ms |
15956 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
15956 KB |
Output is correct |
| 2 |
Correct |
9 ms |
15956 KB |
Output is correct |
| 3 |
Correct |
9 ms |
15956 KB |
Output is correct |
| 4 |
Correct |
8 ms |
15956 KB |
Output is correct |
| 5 |
Correct |
8 ms |
15896 KB |
Output is correct |
| 6 |
Incorrect |
11 ms |
15956 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
