제출 #686433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
686433		GudStonks	관광지 (IZhO14_shymbulak)	C++17	0 / 100	40 ms	10928 KiB

shymbulak

#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];

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;
			}
		}
		else if(used[v] != 3 && to != p){
			cout<<v<<" "<<to<<" "<<used[to]<<endl;
		}
	}
	if(used[v] == 3 || used[v] == 2)
		cic.push_back(v), ver[v] = ti++;
		
}

pair<ll, ll> dfs1(ll v, ll p = -1){
	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;
		}
	}
	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);
}

set<ll>s;

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();
	map<ll, ll>mp;
	for(ll i = 1; i <= n; i++){
		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);
		}
		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);
		s.insert(x.ft);
		mp[x.ft] += x.sd;
	}
	auto it = s.end();it--;
	cout<<mp[*it];
}

int  main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int ttt = 1;
	//cin>>ttt;
	while(ttt--)fun();
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50