oj.uz

Submission #318722

# Submission time Handle Problem Language Result Execution time Memory
318722 2020-11-03T03:20:23 Z Gurban Shymbulak (IZhO14_shymbulak) C++17
100 / 100
 212 ms 19800 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn=2e5+5;
int n,x,y,vis[maxn],par[maxn],now,sz,L[4*maxn],pos,apos;
ll jog[maxn];
pair<int,int>dp[maxn],T[4*maxn],nw;
vector<int>E[maxn],v;

void dfs(int nd,int pr){
	par[nd] = pr;
	vis[nd] = 1;
	for(auto i : E[nd]){
		if(vis[i] == 1 and i != pr and (int)v.size() == 0){
			now = nd; while(now != i) v.push_back(now),now=par[now]; v.push_back(i);
			continue;
		}
		if(i != pr and vis[i] != 1) dfs(i,nd);
	}
	return;
}

void dfs1(int nd,int pr){
	dp[nd] = {0,1};
	vector<pair<int,int>>res;
	map<int,int>m,p;
	for(auto i : E[nd]){
		if(i != pr and vis[i] == 0){
			dfs1(i,nd);
			res.push_back(dp[i]);
			m[dp[i].first] += dp[i].second;
			p[dp[i].first]++;
		}
	}
	if((int)res.size()==0) return;
	jog[(*m.rbegin()).first+1] += (*m.rbegin()).second;
	if(res.size() > 1){
		sort(res.begin(),res.end());
		if(p[res.back().first] > 1){
			ll jg = 0,cnt = 0;
			for(int i = (int)res.size()-1;i >= 0;i--){
				if(res[i].first != res.back().first) break;
				if(i != (int)res.size()-1){ 
					cnt /= res[i+1].second; 
					cnt *= res[i].second;
					cnt += res[i].second*res[i+1].second;
				}
				jg += cnt;
			}
			jog[res.back().first*2+2] += jg;
		}
		else {
			auto t = m.rbegin(); t++;
			jog[(*t).first+(*m.rbegin()).first+2] += 1ll * (*t).second * (*m.rbegin()).second;
		}
	}
	dp[nd] = {(*m.rbegin()).first+1,(*m.rbegin()).second};
}

void prop(int nd){
	T[nd*2].first += L[nd];
	L[nd*2] += L[nd];
	T[nd*2+1].first += L[nd];
	L[nd*2+1] += L[nd];
	L[nd] = 0;
}

void f(int nd){
	if(T[nd*2].first == T[nd*2+1].first) T[nd] = {T[nd*2].first,T[nd*2].second+T[nd*2+1].second};
	else if(T[nd*2].first > T[nd*2+1].first) T[nd] = T[nd*2];
	else T[nd] = T[nd*2+1];
}

void upd(int pos,int val,int val1,int l,int r,int nd){
	if(l == r){
		T[nd].first=val,T[nd].second=val1;
		return;
	}
	prop(nd);
	if(pos <= (l+r)/2) upd(pos,val,val1,l,(l+r)/2,nd*2);
	else upd(pos,val,val1,(l+r)/2+1,r,nd*2+1);
	f(nd);
}

void lupd(int a,int b,int val,int l,int r,int nd){
	if(r < a or l > b) return;
	if(l >= a and r <= b){
		T[nd].first += val;
		L[nd] += val;
		return;
	}
	prop(nd);
	lupd(a,b,val,l,(l+r)/2,nd*2);
	lupd(a,b,val,(l+r)/2+1,r,nd*2+1);
	f(nd);
}

pair<int,int>tap(int a,int b,int l,int r,int nd){
	if(r < a or l > b) return {0,0};
	if(l >= a and r <= b) return T[nd];
	prop(nd);
	pair<int,int>cep=tap(a,b,l,(l+r)/2,nd*2);
	pair<int,int>sag=tap(a,b,(l+r)/2+1,r,nd*2+1);
	if(cep.first == sag.first) return {cep.first,cep.second+sag.second};
	if(cep.first > sag.first) return cep;
	return sag;
}

int dis(int a,int b){
	if(b < a) swap(a,b);
	return min(b-a,a+sz-b);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for(int i = 1;i <= n;i++){
		cin >> x >> y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	dfs(1,0);
	
	memset(vis,0,sizeof(vis));
	for(auto i : v) vis[i] = 1;
	for(auto i : v) dfs1(i,0);

	// for(auto i : v) cout<<i<<' '; cout<<'\n';

	sz = v.size();
	upd(0,dp[v[0]].first,dp[v[0]].second,0,sz-1,1);
	for(int i = 1;i < sz;i++){
		upd(i,dp[v[i]].first+dis(0,i),dp[v[i]].second,0,sz-1,1);
		if(dis(1,i) < dis(0,i)) pos=i;
		if(dis(1,i) == dis(0,i)-1) apos=i;
	}
	if(sz % 2 == 1) apos=-1;
	nw = tap(1,sz-1,0,sz-1,1);
	jog[nw.first+dp[v[0]].first] += 1ll*nw.second*dp[v[0]].second;
	if(apos != -1 and dis(0,apos)+dp[v[apos]].first == nw.first) jog[nw.first+dp[v[0]].first] += 1ll*dp[v[apos]].second*dp[v[0]].second;
	if(apos != -1) apos++;


	for(int i = 1;i < sz-1;i++){
		if(pos == sz) pos = 0;
		if(apos == sz) apos = 0;
		if(pos < i){
			lupd(i,sz-1,-1,0,sz-1,1);
			lupd(0,pos,-1,0,sz-1,1);
			now = pos+1;
			if(dis(now,i) == dis(now,i-1)) now++;
			lupd(now,i-1,1,0,sz-1,1);
		}
		else {
			lupd(i,pos,-1,0,sz-1,1);
			if(dis(0,i) > dis(0,i-1)) lupd(0,i-1,1,0,sz-1,1);
			else if(dis(0,i) == dis(0,i-1)) lupd(1,i-1,1,0,sz-1,1);
			now = pos+1; 
			if(now < sz and dis(i,now) == dis(i-1,now)) now++;
			if(now < sz) lupd(now,sz-1,1,0,sz-1,1);
		}
		nw = tap(i+1,sz-1,0,sz-1,1);
		// cout<< i <<' '<< v[i] << ' '<< nw.first << ' ' << nw.second<<' '<<v[apos]<<'\n';
		jog[nw.first+dp[v[i]].first] += 1ll*nw.second*dp[v[i]].second;
		if(apos != -1 and dis(i,apos)+dp[v[apos]].first == nw.first and apos > i) jog[nw.first+dp[v[i]].first] += 1ll*dp[v[apos]].second*dp[v[i]].second;
		if(apos != -1) apos++;
		pos++;
		// cout<<jog[3]<<'\n';
	}
	for(int i = n;i >= 1;i--) if(jog[i]) return cout<<jog[i],0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 4 ms 5868 KB Output is correct
4 Correct 4 ms 5888 KB Output is correct
5 Correct 4 ms 5868 KB Output is correct
6 Correct 5 ms 5868 KB Output is correct
7 Correct 4 ms 5868 KB Output is correct
8 Correct 4 ms 5868 KB Output is correct
9 Correct 4 ms 5868 KB Output is correct
10 Correct 4 ms 5868 KB Output is correct
11 Correct 4 ms 5868 KB Output is correct
12 Correct 4 ms 5868 KB Output is correct
13 Correct 4 ms 5868 KB Output is correct
14 Correct 5 ms 5868 KB Output is correct
15 Correct 4 ms 5868 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5996 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 5 ms 5996 KB Output is correct
4 Correct 4 ms 5868 KB Output is correct
5 Correct 7 ms 6124 KB Output is correct
6 Correct 6 ms 6252 KB Output is correct
7 Correct 8 ms 6272 KB Output is correct
8 Correct 7 ms 6252 KB Output is correct
9 Correct 7 ms 6124 KB Output is correct
10 Correct 6 ms 6124 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 10596 KB Output is correct
2 Correct 83 ms 11108 KB Output is correct
3 Correct 124 ms 16992 KB Output is correct
4 Correct 59 ms 10980 KB Output is correct
5 Correct 58 ms 10980 KB Output is correct
6 Correct 212 ms 14820 KB Output is correct
7 Correct 131 ms 13540 KB Output is correct
8 Correct 113 ms 15844 KB Output is correct
9 Correct 113 ms 15972 KB Output is correct
10 Correct 103 ms 16868 KB Output is correct
11 Correct 121 ms 18524 KB Output is correct
12 Correct 128 ms 19800 KB Output is correct