Submission #487077

# Submission time Handle Problem Language Result Execution time Memory
487077 2021-11-14T04:05:27 Z kiomi Shymbulak (IZhO14_shymbulak) C++17
50 / 100
1500 ms 30976 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 fill(int u,int v,int pr=0,int d=0,int cnt=0){
	if(diam<d){
		diam=d;
		ans=0;
	}
	if(diam==d&&u<v){
		ans++;
	}
	for(int i=0;i<len(g[v]);i++){
		int to=g[v][i];
		if(to==pr||cnt+(k[to]>0)==2){
			continue;
		}
		fill(u,to,v,d+1,cnt+(k[to]>0));
	}
}
void tea(int v,int pr=0){
	fill(v,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;
		}
		tea(to,v);
		w.push_back({dm[to],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<=n;i++){
		if(k[i]){
			continue;
		}
		fill(i,i);
	}
	for(int i=1;i<=m;i++){
		if(i==1){
			build();
			continue;
		}
		for(int j=1;j<=m;j++){
			upd(j,j,-get(j,j).f+(min(abs(i-j),m-abs(i-j))+dm[q[j]]));
		}
			/*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;
		}
		/*for(int j=1;j<i;j++){
			int de=min(abs(i-j),m-abs(i-j))+dm[q[i]]+dm[q[j]];
			if(diam<de){
				diam=de;
				ans=0;
			}
			if(diam==de){
				ans+=e[q[i]]*e[q[j]];
				if(abs(i-j)==m-abs(i-j)){
					ans+=e[q[i]]*e[q[j]];
				}
			}
		}*/
		//tea(q[i]);
		//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:253:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  253 | 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 12 ms 23868 KB Output is correct
4 Correct 13 ms 23796 KB Output is correct
5 Correct 13 ms 23840 KB Output is correct
6 Correct 13 ms 23768 KB Output is correct
7 Correct 12 ms 23776 KB Output is correct
8 Correct 12 ms 23760 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 12 ms 23756 KB Output is correct
11 Correct 12 ms 23756 KB Output is correct
12 Correct 12 ms 23756 KB Output is correct
13 Correct 12 ms 23844 KB Output is correct
14 Correct 12 ms 23808 KB Output is correct
15 Correct 14 ms 23840 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 126 ms 24000 KB Output is correct
2 Correct 18 ms 23884 KB Output is correct
3 Correct 70 ms 24004 KB Output is correct
4 Correct 14 ms 23948 KB Output is correct
5 Correct 30 ms 24264 KB Output is correct
6 Correct 219 ms 24352 KB Output is correct
7 Correct 406 ms 24388 KB Output is correct
8 Correct 357 ms 24244 KB Output is correct
9 Correct 20 ms 24268 KB Output is correct
10 Correct 85 ms 24140 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 1579 ms 30976 KB Time limit exceeded
2 Halted 0 ms 0 KB -