Submission #1169093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169093		Troll321	Inside information (BOI21_servers)	C++20	5 / 100	3597 ms	45900 KiB

servers

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<bool, bool> pbb;
const ll MAXN = 120000 + 5;
const ll MAXQ = 2*MAXN;
const ll LOG = 17;
const ll MAXLOG = LOG+5;

ll n, k;

pair<char, pll> query[MAXQ];
// {Type, {a, b}}

ll parr[MAXN], depth[MAXN], sz[MAXN], heavy[MAXN];
vector<ll> adjl[MAXN];

struct segment {
	ll root = 0;
	vector<ll> nodes, seg;
	vector<pll> range;
	// {L, R}
	vector<pbb> extend;
	// {Lext, Rext}

	ll getIdx(ll node) {
		return depth[node] - depth[root];
	}

	ll lb() {return 0;}
	ll rb() {return (ll)nodes.size()-1;}

	void addNode(ll node) {
		if(nodes.empty()) {root = node;}
		nodes.push_back(node);
	}

	void addEdge(ll idxa, ll idxb) {
		if(idxa > idxb) {swap(idxa,idxb);}

		// Extend A
		extend[idxa].se = ((range[idxb].se - range[idxb].fi) == 0);

		// Extend B
		extend[idxb].fi = ((range[idxa].se - range[idxa].fi) == 0);

		range[idxa].se = idxb;
		range[idxb].fi = idxa;
	}

	pll findL(ll idx) {
		if(extend[idx].fi && range[idx].fi != idx) {
			pll out = findL(range[idx].fi);
			range[idx].fi = out.fi;
			extend[idx].fi = out.se;
			return {range[idx].fi, extend[idx].fi};
		}
		return {range[idx].fi, extend[idx].fi};
	}
	// {Range, Ext}

	pll findR(ll idx) {
		if(extend[idx].se && range[idx].se != idx) {
			pll out = findR(range[idx].se);
			range[idx].se = out.fi;
			extend[idx].se = out.se;
			return {range[idx].se, extend[idx].se};
		}
		return {range[idx].se, extend[idx].se};
	}

	pll find(ll idx) {
		return {findL(idx).fi, findR(idx).fi};
	}

	bool data(ll idxa, ll idxb) {
		// Apakah idxb nyampe idxa
		pll out = find(idxb);
		return ((out.fi <= idxa && idxa <= out.se) ? true : false);
	}

	ll count(ll idxa) {
		pll out = find(idxa);
		return (out.se - out.fi + 1);
	}

	void build(ll pos, ll l, ll r) {
		if(l == r) {
			seg[pos] = 1;
			return ;
		}
		ll mid = (l+r)/2;
		build(pos*2, l, mid);
		build(pos*2+1, mid+1, r);
		seg[pos] = seg[pos*2] + seg[pos*2+1];
	}

	void init() {
		seg.resize(nodes.size()*4);
		for (int i = 0; i < nodes.size(); ++i) {
			range.push_back({i,i});
			extend.push_back({true,true});
		}
		build(1, lb(), rb());
	}

	void update(ll pos, ll l, ll r, ll idx, ll x) {
		if(l > idx || r < idx) {
			return ;
		}
		if(idx <= l && r <= idx) {
			seg[pos] = x;
			return ;			
		}
		ll mid = (l+r)/2;
		update(pos*2, l, mid, idx, x);
		update(pos*2+1, mid+1, r, idx, x);
		seg[pos] = seg[pos*2] + seg[pos*2+1];
	}

	ll query(ll pos, ll l, ll r, ll idxa, ll idxb) {
		if(l > idxb || r < idxa) {
			return 0;
		}
		if(idxa <= l && r <= idxb) {
			return seg[pos];
		}
		ll mid = (l+r)/2;
		return (
			query(pos*2, l, mid, idxa, idxb) +
			query(pos*2+1, mid+1, r, idxa, idxb)
		);
	}
};

segment segs[MAXN];
void dfs(ll now, ll par) {
	parr[now] = par;
	depth[now] = depth[par]+1;
	sz[now] = 1;

	for(ll nxt : adjl[now]) {
		if(nxt == par) {continue ;}
		dfs(nxt, now);
		sz[now] += sz[nxt];
	}
}

void addHeavy(ll node, ll hidx) {
	segs[hidx].addNode(node);
}

void hld(ll now, ll par) {
	ll mx = -1, nowHeavy = -1;
	for(ll nxt : adjl[now]) {
		if(nxt == par) {continue ;}
		if(sz[nxt] > mx) {
			mx = sz[nxt];
			nowHeavy = nxt;
		}
	}

	if(heavy[now] == 0) {
		if (now == par) {
			heavy[now] = nowHeavy;
			addHeavy(now, heavy[now]);
		} else {
			heavy[now] = now;
			addHeavy(par, heavy[now]);
			addHeavy(now, heavy[now]);
		}
	}

	if(nowHeavy != -1) {
		heavy[nowHeavy] = heavy[now];
		addHeavy(nowHeavy, heavy[now]);
	}

	for(ll nxt : adjl[now]) {
		if(nxt == par) {continue ;}
		hld(nxt, now);
	}
}

void initSegs() {
	for (int i = 1; i <= n; ++i) {
		if(segs[i].nodes.empty()) {continue ;}
		segs[i].init();
	}
}

void addEdge(ll a, ll b) {
	if(depth[a] < depth[b]) {swap(a, b);}
	segment* s = &segs[heavy[a]];
	(*s).addEdge((*s).getIdx(b), (*s).getIdx(a));

	while(true) {
		pll range = (*s).find(0);
		ll ncnt = (*s).query(1, (*s).lb(), (*s).rb(), range.fi, range.se);
		ll now = (*s).root;
		s = &segs[heavy[now]];

		(*s).update(1, (*s).lb(), (*s).rb(), (*s).getIdx(now), ncnt);

		if(heavy[(*s).root] == heavy[now]) {
			break ;
		}
	}
}

void ask(ll a, ll b) {
	// Apakah b mencapai a
	ll ans = -1;
	while(true) {
		if(heavy[a] == heavy[b]) {
			segment* s = &segs[heavy[a]];
			ll ida = (*s).getIdx(a);
			ll idb = (*s).getIdx(b);
			ll hasil = (*s).data(ida, idb);
			ans = hasil;
			break ;
		} else {
			if(depth[heavy[a]] < depth[heavy[b]]) {
				// Naikin B
				segment* s = &segs[heavy[b]];
				ll idb = (*s).getIdx(b);
				ll hasil = (*s).data(0, idb);
				ans = hasil;
				if(!hasil) {break ;}

				b = (*s).root;
			} else {
				// Naikin A
				segment* s = &segs[heavy[a]];
				ll ida = (*s).getIdx(a);
				ll hasil = (*s).data(ida, 0);
				ans = hasil;
				if(!hasil) {break ;}

				a = (*s).root;
			}
		}
	}
	cout << (ans ? "yes" : "no") << "\n";
}

void count(ll a) {
	ll ans = 0;

	while(true) {
		segment* s = &segs[heavy[a]];
		pll range = (*s).find((*s).getIdx(a));
		ll hasil = (*s).query(1, (*s).lb(), (*s).rb(), range.fi, range.se);
		ans += hasil;
		if(range.fi == 0) {
			if(heavy[(*s).root] == heavy[a]) {break ;}
			a = (*s).root;
		}
	}

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

void solve() {
	cin >> n >> k;

	for (int i = 1; i <= n+k-1; ++i) {
		cin >> query[i].fi;
		switch(query[i].fi) {
		case 'S':
			cin >> query[i].se.fi >> query[i].se.se;
			adjl[query[i].se.fi].push_back(query[i].se.se);
			adjl[query[i].se.se].push_back(query[i].se.fi);
			break ;
		case 'Q':
			cin >> query[i].se.fi >> query[i].se.se;
			break ;
		case 'C':
			cin >> query[i].se.fi;
			break ;
		}
	}

	dfs(1, 1);
	hld(1, 1);
	initSegs();

	for (int i = 1; i <= n+k-1; ++i) {
		switch(query[i].fi) {
		case 'S':
			addEdge(query[i].se.fi, query[i].se.se);
			break ;
		case 'Q':
			ask(query[i].se.fi, query[i].se.se);
			break ;
		case 'C':
			count(query[i].se.fi);
			break ;
		}
	}
}

int main() {
	// ios_base::sync_with_stdio(false); cin.tie(0);
	solve();
	return 0;
}

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 5 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18