Submission #487085

# Submission time Handle Problem Language Result Execution time Memory
487085 2021-11-14T04:18:48 Z kiomi Shymbulak (IZhO14_shymbulak) C++17
0 / 100
1500 ms 30916 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);
	}
	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;
				}
			}
		}
	}
}
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]);
	}
	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:242:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  242 | main(){
      | ^~~~
# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 16 ms 23872 KB Output is correct
4 Correct 14 ms 23876 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 16 ms 23860 KB Output is correct
7 Correct 13 ms 23756 KB Output is correct
8 Correct 15 ms 23872 KB Output is correct
9 Correct 14 ms 23788 KB Output is correct
10 Correct 15 ms 23844 KB Output is correct
11 Correct 15 ms 23756 KB Output is correct
12 Correct 13 ms 23756 KB Output is correct
13 Incorrect 13 ms 23784 KB Output isn't correct
14 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 13 ms 23976 KB Output is correct
2 Correct 12 ms 23896 KB Output is correct
3 Correct 17 ms 23912 KB Output is correct
4 Execution timed out 1588 ms 23884 KB Time limit exceeded
5 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1587 ms 30916 KB Time limit exceeded
2 Halted 0 ms 0 KB -