Submission #819276

#	Time	Username	Problem	Language	Result	Execution time	Memory
819276		sentheta	Tourism (JOI23_tourism)	C++17	10 / 100	5087 ms	27828 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;
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){
	auto it = s.insert(i);
	
	// remove prv-nxt
	if(it!=s.begin() && it!=prev(s.end())){
		int prvi = *prev(it), nxti = *next(it);
		pathlen -= getSemipath(prvi, nxti);
	}
	// connect prv-i
	if(it!=s.begin()){
		int prvi = *prev(it);
		pathlen += getSemipath(prvi, i);
	}
	// connect i-nxt
	if(it!=prev(s.end())){
		int nxti = *next(it);
		pathlen += getSemipath(i, nxti);
	}
}
void erase(int i){
	auto it = s.find(i);
	
	// remove prv-i
	if(it!=s.begin()){
		int prvi = *prev(it);
		pathlen -= getSemipath(prvi, i);
	}
	// remove i-nxt
	if(it!=prev(s.end())){
		int nxti = *next(it);
		pathlen -= getSemipath(i, nxti);
	}	
	// connect prv-nxt
	if(it!=s.begin() && it!=prev(s.end())){
		int prvi = *prev(it), nxti = *next(it);
		pathlen += getSemipath(prvi, nxti);
	}
	
	s.erase(it);
}



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;
	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.begin();
		int ri = *prev(s.end());
		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