Submission #819305

#	Time	Username	Problem	Language	Result	Execution time	Memory
819305		sentheta	Tourism (JOI23_tourism)	C++17	10 / 100	5069 ms	24836 KiB

tourism

// author : sentheta aka vanwij
#ifdef VANWIJ
	#include"/home/user/code/bits/stdc++.h"
	#define DBG 1
#else
	#include"bits/stdc++.h"
	#define DBG 0
#endif
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)

#define cerr if(DBG) cout
#define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;}

// #define int long long
// const Int MOD = 1e9+7;
const Int MOD = 998244353;
Int bpow(Int a,Int b){
	Int ret = 1;
	for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD;
	return ret;
}
Int inv(Int a){return bpow(a,MOD-2);}

void solve(); int TC, ALLTC;
signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7);
	// cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0;
	solve();
}














const int N = 1e5+69;
const int LN = 18;
const int SN = 600;
int hilbert(int x, int y){
	int d = 0;
	for(int s=1LL<<(LN-1); s; s>>=1){
		bool rx=x&s, ry=y&s;
		d = d<<2 | rx*3^ry;
		if(!ry){ if(rx){
			x = (1<<LN)-x; y = (1<<LN)-y;
		} swap(x,y); }
	} return d;
}

int n, m, q;
int a[N];


// tree utilities
V<int> adj[N];
int d[N], p[N];
int getMinDepth(int x,int y){
	return d[x]<d[y] ? x : y;
}
int getMaxDepth(int x,int y){
	return d[x]>d[y] ? x : y;
}
struct Stable{
	int v[2*N][LN];
	void build(){
		rep(lg,1,LN) for(int i=0; i+(1<<lg)-1<2*N; i++)
			v[i][lg] = getMinDepth(v[i][lg-1], v[i+(1<<(lg-1))][lg-1]);
	}
	int qry(int l,int r){
		int lg = __lg(r-l+1);
		return getMinDepth(v[l][lg], v[r-(1<<lg)+1][lg]);
	}
} stable;
int t[N], tim;
int getLca(int x,int y){
	if(!(t[x]<t[y])) swap(x,y);
	return stable.qry(t[x],t[y]);
}
void dfs_init(int x=1){
	t[x] = tim;
	stable.v[tim++][0] = x;

	for(int y : adj[x]) if(y!=p[x]){
		d[y] = d[x]+1;
		p[y] = x;
		dfs_init(y);
		
		stable.v[tim++][0] = x;
	}
}

// s = {t[nodes]}
// multiset<int> s;

#define ull unsigned long long
// van Emde Boas tree. Maintains a set of integers in range [0, 2^B) and supports operations
//	findNext(i): returns minimum j >= i in set, or 2^B if none exist
// findPrev(i): returns maximum j <= i in set, or -1 if none exist
//	insert(i), erase(i): insert/erase i into the set
//	empty(): returns TRUE if the set is empty
//	clear(): empties the set
//	init(bts): inits the set, after the call i will be in the set if bts[i] = 1. bts should be a bitset, but can be a vector of 0/1
// All operations except empty, clear and init are O(log B) = O(log log 2^B) with good constants
template<int B, typename ENABLE = void>
class VEBTree {
	private:
		const static int K = B / 2, R = (B + 1) / 2, M = (1 << B);
		const static int S = 1 << K, MASK = (1 << R) - 1;
		array<VEBTree<R>, S> ch;
		VEBTree<K> act;
		int mi, ma;
	public:
		bool empty() const { return ma < mi; }
		
		int findNext(int i) const {
			if (i <= mi) return mi;
			if (i > ma) return M;
			
			int j = i >> R, x = i & MASK;
			int res = ch[j].findNext(x);
			if (res <= MASK) return (j << R) + res;
			
			j = act.findNext(j + 1);
			return (j >= S) ? ma : ((j << R) + ch[j].findNext(0));
		}
		int findPrev(int i) const {
			if (i >= ma) return ma;
			if (i < mi) return -1;
			
			int j = i >> R, x = i & MASK;
			int res = ch[j].findPrev(x);
			if (res >= 0) return (j << R) + res;
			
			j = act.findPrev(j - 1);
			return (j < 0) ? mi : ((j << R) + ch[j].findPrev(MASK));
		}
		void insert(int i) {
			if (i <= mi) {
				if (i == mi) return;
				swap(mi, i);
				if (i == M) ma = mi; // we were empty
				if (i >= ma) return; // we had mi == ma
			} else if (i >= ma) {
				if (i == ma) return;
				swap(ma, i);
				if (i <= mi) return; // we had mi == ma
			}
			int j = i >> R;
			if (ch[j].empty()) act.insert(j);
			ch[j].insert(i & MASK);
		}
		void erase(int i) {
			if (i <= mi) {
				if (i < mi) return;
				i = mi = findNext(mi + 1);
				if (i >= ma) {
					if (i > ma) ma = -1; // we had mi == ma
					return; // after erase we have mi == ma
				}
			} else if (i >= ma) {
				if (i > ma) return;
				i = ma = findPrev(ma - 1);
				if (i <= mi) return; // after erase we have mi == ma
			}
			int j = i >> R;
			ch[j].erase(i & MASK);
			if (ch[j].empty()) act.erase(j);
		}

		void clear() {
			mi = M, ma = -1;
			act.clear();
			for (int i = 0; i < S; ++i) ch[i].clear();
		}
		template<class T>
		void init(const T& bts, int shift = 0, int s0 = 0, int s1 = 0) {
			s0 = -shift + bts.findNext(shift + s0, shift + M-1 - s1);
			s1 = M-1 - (-shift + bts.findPrev(shift + M-1-s1, shift + s0));
			if (s0 + s1 >= M) clear();
			else {
				act.clear();
				mi = s0, ma = M-1 - s1;
				++s0; ++s1;
				for (int j = 0; j < S; ++j) {
					ch[j].init(bts, shift + (j << R), max(0, s0 - (j << R)), max(0, s1 - ((S-1-j) << R)));
					if (! ch[j].empty()) act.insert(j);
				}
			}
		}
};
template<int B>
class VEBTree<B, enable_if_t<(B <= 6)>> {
	private:
		const static int M = (1 << B);
		ull act;
	public:
		bool empty() const { return !act; }
		void clear() { act = 0; }

		int findNext(int i) const {
			return ((i < M) && (act >> i)) ? i + __builtin_ctzll(act >> i) : M;
		}
		int findPrev(int i) const {
			return ((i != -1) && (act << (63 - i))) ? i - __builtin_clzll(act << (63 - i)) : -1;
		}
		void insert(int i) { act |= 1ull << i; }
		void erase(int i) { act &= ~(1ull << i); }
		
		template<class T>
		void init(const T& bts, int shift = 0, int s0 = 0, int s1 = 0) {
			if (s0 + s1 >= M) act = 0;
			else act = bts.getRange(shift + s0, shift + M-1-s1) << s0;
		}
};
#undef ull

VEBTree<LN> s;
int cnt[2*N];
int pathlen = 0;
int getSemipath(int i,int j){
	return d[stable.v[j][0]] - d[stable.qry(i,j)];
	// assert(i <= j);
	// int u = stable.v[i][0];
	// int v = stable.v[j][0];
	// return d[v] - d[getLca(u,v)];
}
void insert(int i){
	cnt[i]++;
	assert(cnt[i]>=0);
	if(cnt[i] > 1) return;
	int prvi = s.findPrev(i);
	int nxti = s.findNext(i);
	s.insert(i);
	
	// remove prv-nxt
	if(prvi!=-1 && nxti!=(1<<LN)){
		pathlen -= getSemipath(prvi, nxti);
	}
	// connect prv-i
	if(prvi!=-1){
		pathlen += getSemipath(prvi, i);
	}
	// connect i-nxt
	if(nxti!=(1<<LN)){
		pathlen += getSemipath(i, nxti);
	}
	
}
void erase(int i){
	cnt[i]--;
	assert(cnt[i]>=0);
	if(cnt[i] >= 1) return;
	s.erase(i);
	int prvi = s.findPrev(i);
	int nxti = s.findNext(i);
	
	// remove prv-i
	if(prvi!=-1){
		pathlen -= getSemipath(prvi, i);
	}
	// remove i-nxt
	if(nxti!=(1<<LN)){
		pathlen -= getSemipath(i, nxti);
	}	
	// connect prv-nxt
	if(prvi!=-1 && nxti!=(1<<LN)){
		pathlen += getSemipath(prvi, nxti);
	}
	
}



int ql[N], qr[N], qans[N];
int qhsh[N];



void solve(){
	
	cin >> n >> m >> q;

	rep(i,0,n-1){
		int u, v;
		cin >> u >> v;
		
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs_init();
	stable.build();
	
	// rep(i,1,n+1) cerr << t[i] << " ";
	// cerr << nl;

	rep(i,1,m+1){
		cin >> a[i];
	}
	
	V<int> ord;
	rep(i,1,q+1){
		cin >> ql[i] >> qr[i];
		
		ord.push_back(i);
		qhsh[i] = hilbert(ql[i], qr[i]);
	}
	sort(all(ord),[&](int i,int j){
		return qhsh[i] < qhsh[j];
		// if(ql[i]/SN==ql[j]/SN) return qr[i] < qr[j];
		// return ql[i]/SN < ql[j]/SN;
	});
	
	
	int l=1, r=1;
	s.clear();
	insert(t[a[1]]);
	for(int i : ord){
		while(ql[i] < l) insert(t[a[--l]]);
		while(r < qr[i]) insert(t[a[++r]]);
		while(l < ql[i]) erase(t[a[l++]]);
		while(qr[i] < r) erase(t[a[r--]]);
		assert(l==ql[i] && r==qr[i]);

		// leftmost and rightmost node
		int li = s.findNext(0);
		int ri = s.findPrev((1<<LN)-1);
		int u = stable.v[li][0];
		int v = stable.v[ri][0];
		int lca = getLca(u,v);
		
		// dbg(pathlen);
		int ans = pathlen + d[u]-d[lca];
		// int ans = pathlen + d[stable.v[li][0]]-d[stable.qry(li,ri)];
		qans[i] = ans;
	}
	
	rep(i,1,q+1){
		cout << qans[i]+1 << nl;
	}



}

Compilation message (stderr)

tourism.cpp: In function 'int hilbert(int, int)':
tourism.cpp:68:18: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   68 |   d = d<<2 | rx*3^ry;
      |              ~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41