Submission #1129224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129224		Math4Life2020	Tourism (JOI23_tourism)	C++20	17 / 100	5109 ms	403952 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 131072; const ll E = 17;
vector<ll> fadj[Nm];
ll radj[Nm];
ll sz[Nm];
ll ht[Nm];
vector<ll> adj[Nm];
bool isHeavy[Nm]; //global memory -> all 0 by default
ll hprt[Nm]; //heavy parent
ll hsz[Nm]; //heavy path size
ll memloc[Nm];
vector<ll> ett; //euler tour
ll floc[Nm];
pii ettmin[2*Nm][E+2]; //{height,xval}
map<ll,ll> hld[2*Nm]; //{elem,count}
bool lazy[2*Nm]; //lazy tag on above
ll ansST[2*Nm];

inline pii fz(pii p1, pii p2) {
	if (p1.first<p2.first) {
		return p1;
	} else {
		return p2;
	}
}

inline ll l2(ll x) {
	return (31-__builtin_clz(x));
}

inline ll v2(ll x) {
	return __builtin_ctz(x);
}

void updT(ll x, ll v) {
	ansST[Nm+x]+=v;
	ll p = (Nm+x)/2;
	while (p>0) {
		ansST[p]=ansST[2*p]+ansST[2*p+1];
		p=p/2;
	}
}

ll qryT(ll x) {
	if (x<0) {
		return 0;
	}
	ll vx = v2(x+1);
	return (ansST[(1LL<<(E-vx))+(x>>vx)]+qryT(x-(1LL<<vx)));
}

ll lca(ll x, ll y) {
	x = floc[x]; y = floc[y];
	if (x>y) {
		swap(x,y);
	}
	ll l2d = l2(y-x+1);
	pii pf = fz(ettmin[x][l2d],ettmin[y-(1LL<<l2d)+1][l2d]);
	return pf.second;
}

void pdn(ll x) {
	if (x>=Nm || !lazy[x]) {
		return;
	}
	lazy[x]=0;
	lazy[2*x]=1;
	lazy[2*x+1]=1;
	auto A0 = hld[x].begin();
	hld[2*x+1]=hld[2*x]=(map<ll,ll>){{(*A0).first,(*A0).second/2}};
}

void lft(ll x) {
	if (x>=Nm || lazy[x]) {
		return;
	}
	map<ll,ll> vf;
	for (pii p0: hld[2*x]) {
		vf[p0.first]+=p0.second;
	}
	for (pii p0: hld[2*x+1]) {
		vf[p0.first]+=p0.second;
	}
	hld[x]=vf;
}

void stset(ll p, ll sz0, ll t) {
	for (pii p0: hld[p]) {
		if (p0.first==-1) {
			continue;
		}
		updT(p0.first,-p0.second);
		ll pc = p/2;
		while (pc>0) {
			//auto A0 = hld[pc].find(p0.first);
			hld[pc][p0.first]-=p0.second;
			pc=pc/2;
		}
		//cerr << "updT: t,val="<<p0.first<<","<<(-p0.second)<<"\n";
	}
	hld[p]=(map<ll,ll>){{t,sz0}};
	ll pc = p/2;
	while (pc>0) {
		hld[pc][t]+=sz0;
		pc=pc/2;
	}
	updT(t,sz0);
	//cerr << "updT: t,val="<<t<<","<<sz0<<"\n";
	lazy[p]=1;
}

void updR(ll x, ll y, ll t) { //set segtree elements in [x,y] to all t
	//return;
	//cout << "updR on x,y,t="<<x<<","<<y<<","<<t<<"\n";
	if (x>y) {
		return;
	}
	for (ll e=E;e>=0;e--) {
		pdn((x>>e)+(1LL<<(E-e)));
		pdn((y>>e)+(1LL<<(E-e)));
	}
	ll xc = x; ll yc = y;
	while (xc<=yc) {
		ll vx = v2(xc); ll vy = v2(yc+1);
		if (vx<vy) {
			stset((xc>>vx)+(1LL<<(E-vx)),(1LL<<vx),t);
			xc += (1LL<<vx);
		} else {
			stset((yc>>vy)+(1LL<<(E-vy)),(1LL<<vy),t);
			yc -= (1LL<<vy);
		}
	}
	// bool lzyF = 0;
	// for (ll e=0;e<=E;e++) {
	// 	ll p = (x>>e)+(1LL<<(E-e));
	// 	if (lzyF) {
	// 		lft(p);
	// 	} else {
	// 		if (lazy[p]) {
	// 			lzyF=1;
	// 		}
	// 	}
	// }
	// lzyF=0;
	// for (ll e=0;e<=E;e++) {
	// 	ll p = (y>>e)+(1LL<<(E-e));
	// 	if (lzyF) {
	// 		lft(p);
	// 	} else {
	// 		if (lazy[p]) {
	// 			lzyF=1;
	// 		}
	// 	}
	// }
}

//ll CLOCK = 0;

void upd(ll x, ll y, ll t) { //update path x->y, set to time t
	//cout << "upd: x,y,t="<<x<<","<<y<<","<<t<<"\n";
	// if (100<=CLOCK++) {
	// 	return;
	// }
	//return;
	if (ht[x]<ht[y] || x<0) {
		return;
	}
	if (ht[hprt[x]]>=ht[y]) {
		updR(memloc[hprt[x]],memloc[hprt[x]]+ht[x]-ht[hprt[x]],t);
		upd(radj[hprt[x]],y,t);
	} else {
		updR(memloc[hprt[x]]+ht[y]-ht[hprt[x]],memloc[hprt[x]]+ht[x]-ht[hprt[x]],t);
	}
}


int main() {
	ll N,M,Q;
	ios_base::sync_with_stdio(false); cin.tie(0);
 	cin >> N >> M >> Q;
	if (N==1) {
		for (ll q=0;q<Q;q++) {
			cout << "1\n";
		}
		exit(0);
	}
	for (ll i=0;i<(N-1);i++) {
		ll a,b; cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	radj[0]=-1;
	ht[0]=0;
	queue<ll> q0;
	vector<ll> rtpls;
	q0.push(0);
	while (!q0.empty()) {
		ll x = q0.front(); q0.pop();
		for (ll y: adj[x]) {
			if (y != radj[x]) {
				ht[y]=1+ht[x];
				radj[y]=x;
				fadj[x].push_back(y);
				q0.push(y);
				rtpls.push_back(y);
			}
		}
	}
	for (ll t=(N-1);t>=0;t--) {
		ll x = rtpls[t];
		hprt[x]=x;
		sz[x]=1;
		ll maxsz=-1; ll cstr=-1;
		for (ll y: fadj[x]) {
			sz[x]+=sz[y];
			if (sz[y]>maxsz) {
				cstr = y; maxsz = sz[y];
			}
		}
		if (cstr!=-1) {
			isHeavy[cstr]=1;
		}
	}
	for (ll t=0;t<N;t++) {
		ll x = rtpls[t];
		if (isHeavy[x]) {
			hprt[x]=hprt[radj[x]];
			hsz[hprt[x]]++;
		}
	}
	ll MLOC = 0; //memory location
	for (ll t=0;t<N;t++) {
		ll x = rtpls[t];
		if (!isHeavy[x]) {
			memloc[x]=MLOC;
			hsz[x]++;
			MLOC += hsz[x];
		}
	}
	stack<pii> s0;
	s0.push({0,0});
	while (!s0.empty()) {
		pii p0 = s0.top(); s0.pop();
		ll x = p0.first; ll t = p0.second;
		ett.push_back(x);
		if (t==0) {
			floc[x]=ett.size()-1;
			for (ll y: fadj[x]) {
				s0.push({x,1});
				s0.push({y,0});
			}
		} 
	}
	assert(ett.size()<=(2*Nm));
	for (ll t=0;t<ett.size();t++) {
		ettmin[t][0]={ht[ett[t]],ett[t]};
	}
	for (ll t=(ett.size());t<(2*Nm);t++) {
		ettmin[t][0]={0,0};
	}
	for (ll e=1;e<=(E+1);e++) {
		for (ll t=0;t<=(2*Nm-(1LL<<e));t++) {
			ettmin[t][e]=fz(ettmin[t][e-1],ettmin[t+(1LL<<(e-1))][e-1]);
		}
	}
	for (ll t=1;t<(2*Nm);t++) {
		hld[t]=(map<ll,ll>){{-1,(1LL<<(E-l2(t)))}};
	}
	vector<ll> cv;
	for (ll i=0;i<M;i++) {
		ll ci; cin >> ci; ci--;
		cv.push_back(ci);
	}
	vector<pair<ll,pii>> qryV; //{r,{l,qi}}
	ll ans[Q];
	for (ll q=0;q<Q;q++) {
		ll l,r; cin >> l >> r;
		l--; r--;
		qryV.push_back({r,{l,q}});
	}
	sort(qryV.begin(),qryV.end());
	ll TR = 0;
	//upd(cv[0],cv[0],0);
	//cerr << "end op\n";
	// cout << "ett vector:\n";
	// for (ll x: ett) {
	// 	cout << x << " ";
	// }
	// cout << "\nfloc vector:\n";
	// for (ll x=0;x<N;x++) {
	// 	cout << floc[x]<<" ";
	// }
	// exit(0);
	// for (ll x=0;x<N;x++) {
	// 	cout << "x="<<x<<"\n";
	// 	cout << "isHeavy[x]="<<isHeavy[x]<<"\n";
	// 	cout << "memloc[x]="<<memloc[x]<<"\n";
	// }
	for (auto A: qryV) {
		ll r = A.first; ll l = A.second.first; ll q = A.second.second;
		if (r>TR) {
			while (r!=TR) {
				ll clca = lca(cv[TR],cv[TR+1]);
				//cout << "cv[TR],cv[TR+1],clca="<<cv[TR]<<","<<cv[TR+1]<<","<<clca<<"\n";
				upd(cv[TR],clca,TR+1);
				//cout << "end op\n";
				//cerr << "end op\n";
				upd(cv[TR+1],clca,TR+1);
				//cout << "end op\n";
				//cerr << "end op\n";
				TR++;
			}
		}
		ll ansv = 0;
		ansv += qryT(r);
		ansv -= qryT(l);
		if (l==r) {
			ansv=1;
		}
		ans[q]=ansv;
	}
	for (ll m=0;m<=M;m++) {
		//cout << "qryT(t="<<m<<")="<<qryT(m)<<"\n";
		//cout << "ansST[Nm+t]="<<ansST[Nm+m]<<"\n";
	}
	for (ll q=0;q<Q;q++) {
		cout << ans[q] << "\n";
	}
}

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