Submission #487090

# Submission time Handle Problem Language Result Execution time Memory
487090 2021-11-14T04:41:55 Z kiomi Shymbulak (IZhO14_shymbulak) C++17
100 / 100
195 ms 43728 KB
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("Ofast")
//#pragma GCC optimization ("unroll-loops")

//#pragma comment(linker,"/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define full(x,n) x,x+n+1
#define full(x) x.begin(),x.end()
#define finish return 0

#define putb push_back
#define f first
#define s second

//logx(a^n)=loga(a^n)/logx(a)
//logx(a*b)=logx(a)+logx(b)
//logx(y)=log(y)/log(x)
//logb(n)=loga(n)/loga(b)

#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define putf push_front
#define gainb pop_back

//(a+b)^n=sum of C(n,i)*a^i*b^(n-i) 0<=i<=n
//(a-b)^n=sum of C(n,i)*a^i*b^(n-i) for even i-for odd i

#define gainf pop_front
#define len(x) (int)x.size()

// 1/b%mod=b^(m-2)%mod
// (a>>x)&1==0
// a^b=(a+b)-2(a&b)

typedef double db;
typedef long long ll;
#define int long long

//sum of squares n*(n+1)*(2n+1)/6
//sum of cubes [n*(n+1)/2]^2
//sum of squares for odds n*(4*n*n-1)/3
//sum of cubes for odds n*n*(2*n*n-1)

const int ary=1e6+5;
const ll mod=1e9+7;
const ll inf=1e18;

using namespace std;
using namespace __gnu_pbds;
int n,m,c[ary],p[ary],e[ary],d[ary],dm[ary],k[ary],md[4*ary],diam,ans,q[ary];
vector<int> g[ary];
vector< pair<int,int> > w;
pair<int,int> r[ary];
pair<int,int> t[4*ary];
bool dfs(int v=1,int pr=0){
	c[v]=1;
	for(int i=0;i<len(g[v]);i++){
		int to=g[v][i];
		if(to==pr){
			continue;
		}
		if(c[to]==0){
			p[to]=v;
			if(dfs(to,v)){
				return 1;
			}
		}
		else if(c[to]==1){
			int u=v;
			while(1){
				m++;
				q[m]=u;
				k[u]=m;
				if(u==to){
					break;
				}
				u=p[u];
			}
			return 1;
		}
	}
	c[v]=2;
	return 0;
}
void go(int v,int pr=0){
	dm[v]=d[v]=d[pr]+1;
	e[v]=1;
	for(int i=0;i<len(g[v]);i++){
		int to=g[v][i];
		if(to==pr||k[to]){
			continue;
		}
		go(to,v);
		if(dm[v]<dm[to]){
			e[v]=0;
			dm[v]=dm[to];
		}
		if(dm[v]==dm[to]){
			e[v]+=e[to];
		}
	}
}
void push(int v,bool ok){
	if(md[v]!=0){
		t[v].f+=md[v];
		if(ok){
			md[v*2]+=md[v];
			md[v*2+1]+=md[v];
		}
		md[v]=0;
	}
}
void build(int v=1,int tl=1,int tr=m){
	if(tl==tr){
		t[v]={dm[q[tl]]+min(tl-1,m-(tl-1)),e[q[tl]]};
		return;
	}
	int tm=(tl+tr)/2;
	build(v*2,tl,tm);
	build(v*2+1,tm+1,tr);
	if(t[v*2].f<t[v*2+1].f){
		t[v]=t[v*2+1];
	}
	else if(t[v*2].f>t[v*2+1].f){
		t[v]=t[v*2];
	}
	else{
		t[v]={t[v*2].f,t[v*2].s+t[v*2+1].s};
	}
}
void upd(int l,int r,int x,int v=1,int tl=1,int tr=m){
	push(v,(tl<tr));
	if(tr<l||tl>r||l>r){
		return;
	}
	if(l<=tl&&tr<=r){
		md[v]+=x;
		push(v,(tl<tr));
		return;
	}
	int tm=(tl+tr)/2;
	upd(l,r,x,v*2,tl,tm);
	upd(l,r,x,v*2+1,tm+1,tr);
	if(t[v*2].f<t[v*2+1].f){
		t[v]=t[v*2+1];
	}
	else if(t[v*2].f>t[v*2+1].f){
		t[v]=t[v*2];
	}
	else{
		t[v]={t[v*2].f,t[v*2].s+t[v*2+1].s};
	}
}
pair<int,int> get(int l,int r,int v=1,int tl=1,int tr=m){
	push(v,(tl<tr));
	if(tr<l||r<tl||l>r){
		return {0,0};
	}
	if(l<=tl&&tr<=r){
		return t[v];
	}
	int tm=(tl+tr)/2;
	pair<int,int> a=get(l,r,v*2,tl,tm);
	pair<int,int> b=get(l,r,v*2+1,tm+1,tr);
	if(a.f<b.f){
		return b;
	}
	else if(a.f>b.f){
		return a;
	}
	else{
		return {a.f,a.s+b.s};
	}
}
void func(int i,int x,int y){
	if(i+x-1<=m){
		upd(i,i+x-1,y);
	}
	else{
		upd(i,m,y);
		upd(1,x-(m-i+1),y);
	}
}
void tea(int v,int pr=0){
	for(int i=0;i<len(g[v]);i++){
		int to=g[v][i];
		if(to==pr||k[to]){
			continue;
		}
		tea(to,v);
	}
	w.clear();
	for(int i=0;i<len(g[v]);i++){
		int to=g[v][i];
		if(to==pr||k[to]){
			continue;
		}
		w.push_back({dm[to]-d[v],e[to]});
	}
	sort(full(w));
	reverse(full(w));
	if(len(w)==1){
		if(diam<w.back().f){
			diam=w.back().f;
			ans=0;
		}
		if(diam==w.back().f){
			ans+=w.back().s;
		}
	}
	else if(len(w)>1){
		if(diam<w[0].f+w[1].f){
			diam=w[0].f+w[1].f;
			ans=0;
		}
		if(diam==w[0].f+w[1].f){
			int cnt=w[0].s;
			for(int i=1;i<len(w);i++){
				if(w[i].f==w[1].f){
					ans+=cnt*w[i].s;
				}
				if(w[i].f==w[0].f){
					cnt+=w[i].s;
				}
			}
		}
	}
}
int bfs(int v){
	deque< int > q;
	q.push_back(v);
	int mx=v;
	while(len(q)){
		int u=q[0];
		if(c[u]>c[mx]){
			mx=u;
		}
		q.pop_front();
		for(int i=0;i<len(g[u]);i++){
			int to=g[u][i];
			if(c[to]||to==v){
				continue;
			}
			c[to]=c[v]+1;
			q.push_back(to);
		}
	}
	return mx;
}
main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs();
	d[0]=-1;
	for(int i=1;i<=m;i++){
		go(q[i]);
	}
	int s=bfs(1);
	for(int i=1;i<=n;i++){
		c[i]=0;
	}
	diam=c[bfs(s)];
	for(int i=1;i<=m;i++){
		tea(q[i]);
		if(i==1){
			build();
			continue;
		}
			int x=m/2;
			int y=m-x;
			func(i,x,-1);
			if(y==x){
				func(i+x-m*(i+x>m),y,1);
			}
			else{
				func(i+x+1-m*(i+x+1>m),y-1,1);
			}
		r[i]=get(1,i-1);
		if(diam<r[i].f+dm[q[i]]){
			diam=r[i].f+dm[q[i]];
			ans=0;
		}
		if(diam==r[i].f+dm[q[i]]){
			if(m%2==0&&i-m/2>=1){
				if(diam==dm[q[i]]+dm[q[i-m/2]]+m/2){
					ans+=e[q[i]]*e[q[i-m/2]];
				}
			}
			ans+=e[q[i]]*r[i].s;
		}
		//cout<<i<<" "<<q[i]<<" "<<r[i].f<<" "<<r[i].s<<" "<<e[q[i]]<<" "<<dm[q[i]]<<" "<<d[q[i]]<<" "<<m%2<<" "<<i-m/2<<" "<<diam<<" "<<dm[q[i-m/2]]<<" "<<e[q[i-m/2]]<<"\n";
	}
	cout<<ans;
}

Compilation message

shymbulak.cpp:15: warning: "full" redefined
   15 | #define full(x) x.begin(),x.end()
      | 
shymbulak.cpp:14: note: this is the location of the previous definition
   14 | #define full(x,n) x,x+n+1
      | 
shymbulak.cpp:256:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  256 | main(){
      | ^~~~
# Verdict Execution time Memory Grader output
1 Correct 11 ms 23756 KB Output is correct
2 Correct 11 ms 23788 KB Output is correct
3 Correct 11 ms 23840 KB Output is correct
4 Correct 13 ms 23868 KB Output is correct
5 Correct 11 ms 23756 KB Output is correct
6 Correct 11 ms 23872 KB Output is correct
7 Correct 14 ms 23756 KB Output is correct
8 Correct 13 ms 23872 KB Output is correct
9 Correct 12 ms 23756 KB Output is correct
10 Correct 11 ms 23756 KB Output is correct
11 Correct 11 ms 23756 KB Output is correct
12 Correct 11 ms 23828 KB Output is correct
13 Correct 11 ms 23884 KB Output is correct
14 Correct 11 ms 23884 KB Output is correct
15 Correct 11 ms 23884 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 12 ms 24012 KB Output is correct
2 Correct 11 ms 23908 KB Output is correct
3 Correct 11 ms 23900 KB Output is correct
4 Correct 11 ms 23948 KB Output is correct
5 Correct 13 ms 24268 KB Output is correct
6 Correct 13 ms 24464 KB Output is correct
7 Correct 17 ms 24296 KB Output is correct
8 Correct 13 ms 24268 KB Output is correct
9 Correct 12 ms 24268 KB Output is correct
10 Correct 12 ms 24140 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 64 ms 31504 KB Output is correct
2 Correct 61 ms 32156 KB Output is correct
3 Correct 93 ms 38764 KB Output is correct
4 Correct 48 ms 31940 KB Output is correct
5 Correct 49 ms 31424 KB Output is correct
6 Correct 195 ms 38980 KB Output is correct
7 Correct 105 ms 35440 KB Output is correct
8 Correct 97 ms 39236 KB Output is correct
9 Correct 107 ms 38332 KB Output is correct
10 Correct 89 ms 41884 KB Output is correct
11 Correct 91 ms 42988 KB Output is correct
12 Correct 114 ms 43728 KB Output is correct