Submission #686479

# Submission time Handle Problem Language Result Execution time Memory
686479 2023-01-25T10:31:29 Z GudStonks Shymbulak (IZhO14_shymbulak) C++17
0 / 100
41 ms 9796 KB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ft first
#define sd second
const ll MOD = 1e9+7;
ll n, used[200005], ver[200005], z[1000010], ti = 1;
vector<ll>g[200005], cic;
pair<ll, ll>t[1000010], arr[200005], res;

void add(ll x, ll c){
	if(x > res.ft)
		res = {x, c};
	else if(x == res.ft)
		res.sd += c;
}

void dfs(ll v = 1, ll p = -1){
	used[v] = 1;
	for(auto to : g[v]){
		if(used[to] == 1 && to != p){
			used[to] = 3;
			used[v] = 2;
		}
		else if(used[to] == 0){
			dfs(to, v);
			if(used[to] == 2 && used[v] != 3){
				used[v] = 2;
			}
		}
	}
	if(used[v] == 3 || used[v] == 2)
		cic.push_back(v), ver[v] = ti++;
}

pair<ll, ll> dfs1(ll v, ll p = -1){
	pair<ll, ll>mxx = {0, 0}, mmxx = {0, 0};
	ll mx = 0, c = 1;
	for(auto to : g[v]){
		if(to != p && used[to] == 1){
			auto xx = dfs1(to, v);
			if(xx.ft > mx)
				mx = xx.ft, c = xx.sd;
			else if(xx.ft == mx)
				c += xx.sd;
			if(xx.ft > mxx.ft || (xx.ft == mxx.ft && xx.sd > mxx.sd)){
				mmxx = mxx;
				mxx = {xx.ft, xx.sd};
			}
			else if(xx.ft > mmxx.ft || (xx.ft == mmxx.ft && xx.sd > mmxx.sd))
				mmxx = {xx.ft, xx.sd};
		}
	}
	add(mxx.ft + mmxx.ft, mxx.sd * mmxx.sd);
	return {mx + 1, c};
}

pair<ll, ll> combine(pair<ll, ll>l, pair<ll, ll>r){
	if(l.ft > r.ft)
		return l;
	else if(r.ft > l.ft)
		return r;
	else
		return {l.ft, l.sd + r.sd};
}

void build(ll v = 1, ll tl = 1, ll tr = n){
	if(tl == tr)
		t[v] = arr[tl];
	else{
		ll tm = (tl + tr) / 2;
		build(v + v, tl, tm);
		build(v + v + 1, tm + 1, tr);
		t[v] = combine(t[v + v], t[v + v + 1]);
	}
}

void prp(ll v){
	t[v].ft += z[v];
	if(v + v <= 8e5){
		z[v + v] += z[v];
		z[v + v + 1] += z[v];
	}
	z[v] = 0;
}

pair<ll, ll> get(ll l, ll r, ll v = 1, ll tl = 1, ll tr = n){
	prp(v);
	if(tl > r || tr < l)
		return {0, 0};
	if(l <= tl && tr <= r)
		return t[v];
	ll tm = (tl + tr) / 2;
	return combine(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
}

void upd(ll l, ll r, ll val, ll v = 1, ll tl = 1, ll tr = n){
	prp(v);
	if(tl > r || tr < l)
		return;
	if(l <= tl && tr <= r){
		z[v] += val;
		prp(v);
		return;
	}
	ll tm = (tl + tr) / 2;
	upd(l, r, val, v + v, tl, tm);
	upd(l, r, val, v + v + 1, tm + 1, tr);
}

void upd1(ll pos, bool mode, ll v = 1 , ll tl = 1, ll tr = n){
	if(tl == tr){
		if(mode)
			t[v].sd <<= 1;
		else
			t[v].sd >>= 1;
		return;
	}
	ll tm = (tl + tr) / 2;
	if(tm <= pos)
		upd1(pos, mode, v + v, tl, tm);
	else
		upd1(pos, mode, v + v + 1, tm + 1, tr);
}

void fun(){
	cin>>n;
	for(ll i = 1, a, b; i <= n; i++){
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs();
	for(auto it : cic)
		arr[ver[it]] = dfs1(it), arr[ver[it]].ft--;
	n = cic.size();
	for(ll i = 2; i <= n; i++)arr[i].ft += min(i - 1, n - i + 1);
	build();
	for(ll i = 1; i <= n; i++){
		ll xxx = ((i + (n / 2) - 1 + n) % n) + 1;
		if(i > 1){
			if(i + (n / 2) - 1 > n)
				upd(i, n, -1), upd(1, i + (n / 2) - 1 - n, -1);
			else
				upd(i, i + (n / 2) - 1, -1);

			ll xx = (((i - n / 2) - 1 + n) % n) + 1;
			if(xx + (n / 2) - 1 > n)
				upd(xx, n, 1), upd(1, xx + (n / 2) - 1 - n, 1);
			else
				upd(xx, xx + (n / 2) - 1, 1);
			if(n % 2 == 0)upd1(xxx, 1);
		}
		pair<ll, ll> x;
		if(i == 1)
			x = get(2, n);
		else if(i < n)
			x = combine(get(1, i - 1), get(i + 1, n));
		else
			x = get(1, n - 1);
		add(x.ft, x.sd * arr[i].sd);
		if(i > 1 && n % 2 == 0)
			upd1(xxx, 0);
	}
	cout<<res.sd<<endl;
}

int  main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int ttt = 1;
	//cin>>ttt;
	while(ttt--)fun();
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 5204 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 41 ms 9772 KB Output is correct
2 Incorrect 40 ms 9796 KB Output isn't correct
3 Halted 0 ms 0 KB -