Submission #1241763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241763		altern23	Shymbulak (IZhO14_shymbulak)	C++20	0 / 100	28 ms	11336 KiB

shymbulak

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 2e5;
const ll INF = 1e18;
const int MOD = 998244353;
const ld eps = 1e-6;	

ll vis[MAXN + 5], cycle[MAXN + 5];

vector<ll> adj[MAXN + 5];
ll p[MAXN + 5], st, en;
ll d[MAXN + 5], cur_mx, cur_cnt;

void dfs2(ll idx, ll par){
	vis[idx] = 1;
	if(cur_mx < d[idx]){
		cur_mx = d[idx], cur_cnt = 1;
	}
	else if(cur_mx == d[idx]){
		cur_cnt++;
	}
	for(auto i : adj[idx]){
		if(!vis[i] && !cycle[i]){
			d[i] = d[idx] + 1;
			dfs2(i, idx);
		}
	}
}

void dfs(ll idx, ll par){
	vis[idx] = 1;
	for(auto i : adj[idx]){
		if(i == par) continue;
		if(vis[i]) st = i, en = idx;
		else{
			p[i] = idx;
			dfs(i, idx);
		}
	}
}

struct node{
	ll MX, cnt;
};

struct ST{
	ll N;
	vector<node> sg;
	ST(ll _n){
		N = _n;
		sg.resize(4 * N + 5);
		for(int i = 0; i <= 4 * N; i++) sg[i] = {-INF, 0};
	}
	node comb(node a, node b){
		node c;
		if(a.MX == b.MX) c = {a.MX, a.cnt + b.cnt};
		else if(a.MX > b.MX) c = a;
		else c = b;
		
		return c;
	}
	void upd(ll l, ll r, ll cur, ll idx, node val){
		if(l == r){
			sg[cur] = val;
		}
		else{
			ll mid = (l + r) / 2;
			if(idx <= mid) upd(l, mid, cur * 2, idx, val);
			else upd(mid + 1, r, cur * 2 + 1, idx, val);
			sg[cur] = comb(sg[cur * 2], sg[cur * 2 + 1]);
		}
	}
	node query(ll l, ll r, ll cur, ll x, ll y){
		if(l > y || r < x) return {-INF, 0};
		if(l >= x && r <= y) return sg[cur];
		ll mid = (l + r) / 2;
		return comb(query(l, mid, cur * 2, x, y), query(mid + 1, r, cur * 2 + 1, x, y));
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);		
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N; cin >> N;
		for(int i = 1; i <= N; i++){
			ll u, v; cin >> u >> v;
			adj[u].push_back(v), adj[v].push_back(u);
		}
		dfs(1, -1);
		
		ll sz = 1;
		d[st] = 0;
		while(st != en){
			cycle[st] = 1;
			d[p[st]] = d[st] + 1;
			sz++;
			st = p[st];
		}
		cycle[en] = 1;
		
		vector<pii> v;
		ST pos(sz), neg(sz);
		for(int i = 1; i <= N; i++) vis[i] = 0;
		
		ll cur = 0, ans = 0;
		for(int tt = 1; tt <= N; tt++){
			if(cycle[tt]){
				cur_mx = cur_cnt = 0;
				dfs2(tt, -1);
				v.push_back({d[tt], cur_mx - d[tt]});
				ll i = d[tt], j = cur_mx - d[tt];
				ll batas = i - sz / 2;
				
				if(batas < 0){
					node now = neg.query(0, sz - 1, 1, 0, i);
					if(cur < now.MX + i + j){
						ans = now.cnt * cur_cnt;
						cur = now.MX + i + j;
					}
					else if(cur == now.MX + i + j){
						ans += now.cnt * cur_cnt;
					}
					now = neg.query(0, sz - 1, 1, sz + batas, sz - 1);
					if(cur < now.MX + sz + i + j){
						ans = now.cnt * cur_cnt;
						cur = now.MX + sz + i + j;
					}
					else if(cur == now.MX + sz + i + j){
						ans += now.cnt * cur_cnt;
					}				
					now = pos.query(0, sz - 1, 1, i, sz + batas - 1);
					if(cur < now.MX - i + j){
						ans = now.cnt * cur_cnt;
						cur = now.MX - i + j;
					}
					else if(cur == now.MX - i + j){
						ans += now.cnt * cur_cnt;
					}
					if(sz % 2 == 0){
						now = pos.query(0, sz - 1, 1, i - sz / 2 + sz, i - sz / 2 + sz);
						if(cur < now.MX - i + j){
							ans = now.cnt * cur_cnt;
							cur = now.MX - i + j;
						}
						else if(cur == now.MX - i + j){
							ans += now.cnt * cur_cnt;
						}
					}
				}
				else{
					node now = neg.query(0, sz - 1, 1, batas, i);
					if(cur < now.MX + i + j){
						ans = now.cnt * cur_cnt;
						cur = now.MX + i + j;
					}
					else if(cur == now.MX + i + j){
						ans += now.cnt * cur_cnt;
					}
					now = pos.query(0, sz - 1, 1, 0, batas - 1);
					if(cur < now.MX + sz - i + j){
						ans = now.cnt * cur_cnt;
						cur = now.MX + sz - i + j;
					}
					else if(cur == now.MX + sz - i + j){
						ans += now.cnt * cur_cnt;
					}
					now = pos.query(0, sz - 1, 1, i, sz);
					if(cur < now.MX - i + j){
						ans = now.cnt * cur_cnt;
						cur = now.MX - i + j;
					}
					else if(cur == now.MX - i + j){
						ans += now.cnt * cur_cnt;
					}	
					if(sz % 2 == 0){
						now = pos.query(0, sz - 1, 1, i - sz / 2, i - sz / 2);
						if(cur < now.MX + i + j){
							ans = now.cnt * cur_cnt;
							cur = now.MX + i + j;
						}
						else if(cur == now.MX + i + j){
							ans += now.cnt * cur_cnt;
						}
					}			
				}
				
				pos.upd(0, sz - 1, 1, i, {cur_mx, cur_cnt});
				neg.upd(0, sz - 1, 1, i, {cur_mx - 2 * i, cur_cnt});
			}
		}

		cout << ans << "\n";
	}
}

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