oj.uz

답안 #487087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
487087 2021-11-14T04:21:03 Z kiomi 관광지 (IZhO14_shymbulak) C++17
100 / 100
 171 ms 46132 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;
				}
			}
		}
	}
}
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:235:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  235 | main(){
      | ^~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 12 ms 23756 KB Output is correct
3 Correct 14 ms 23876 KB Output is correct
4 Correct 12 ms 23756 KB Output is correct
5 Correct 12 ms 23756 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 12 ms 23756 KB Output is correct
8 Correct 13 ms 23792 KB Output is correct
9 Correct 12 ms 23816 KB Output is correct
10 Correct 14 ms 23756 KB Output is correct
11 Correct 13 ms 23756 KB Output is correct
12 Correct 13 ms 23872 KB Output is correct
13 Correct 13 ms 23884 KB Output is correct
14 Correct 13 ms 23884 KB Output is correct
15 Correct 13 ms 23908 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 24012 KB Output is correct
2 Correct 12 ms 23924 KB Output is correct
3 Correct 13 ms 23944 KB Output is correct
4 Correct 12 ms 23884 KB Output is correct
5 Correct 13 ms 24156 KB Output is correct
6 Correct 14 ms 24376 KB Output is correct
7 Correct 13 ms 24268 KB Output is correct
8 Correct 14 ms 24268 KB Output is correct
9 Correct 16 ms 24268 KB Output is correct
10 Correct 18 ms 24212 KB Output is correct

Subtask #3
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 31080 KB Output is correct
2 Correct 65 ms 32840 KB Output is correct
3 Correct 93 ms 39872 KB Output is correct
4 Correct 48 ms 32852 KB Output is correct
5 Correct 47 ms 32196 KB Output is correct
6 Correct 171 ms 40896 KB Output is correct
7 Correct 112 ms 36684 KB Output is correct
8 Correct 86 ms 41100 KB Output is correct
9 Correct 84 ms 39684 KB Output is correct
10 Correct 105 ms 44248 KB Output is correct
11 Correct 93 ms 45292 KB Output is correct
12 Correct 100 ms 46132 KB Output is correct