Submission #1303758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303758		namhh	Tourism (JOI23_tourism)	C++20	0 / 100	219 ms	9444 KiB

tourism

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e5+5;
int n,m,q,c[N],st[4*N],lazy[4*N],sz[N],h[N],head[N],heavy[N],par[N],bits[N],ans[N],sta[N],timer = 1;
vector<int>adj[N];
vector<pii>events[N];
void update(int u, int val){
	while(u > 0){
		bits[u] += val;
		u -= u & (-u);
	}
}
int get(int u){
	int res = 0;
	while(u <= n){
		res += bits[u];
		u += u & (-u);
	}
	return res;
}
void pre(int u, int p){
	sz[u] = 1;
	par[u] = p;
	h[u] = h[p]+1;
	for(int v: adj[u]){
		if(v != p){
			pre(v,u);
			sz[u] += sz[v];
			if(sz[heavy[u]] < sz[v]) heavy[u] = v;
		}
	}
}
void dfs(int u, int p){
	sta[u] = timer;
	timer++;
	head[u] = p;
	if(heavy[u]) dfs(heavy[u],p);
	for(int v: adj[u]){
		if(v != par[u] && v != heavy[u]) dfs(v,v);
	}
}
void down(int id){
	if(lazy[id] != 0){
		st[2*id] = lazy[id];
		st[2*id+1] = lazy[id];
		lazy[2*id] = lazy[id];
		lazy[2*id+1] = lazy[id];
		lazy[id] = 0;
	}
}
void update(int id, int l, int r, int u, int v, int val){
	if(l > v || r < u) return;
	if(l >= u && r <= v && (st[id] != -1 || l == r)){
		if(st[id] > 0) update(st[id],-(r-l+1));
		st[id] = val;
		lazy[id] = val;
		update(val,r-l+1);
		return;
	}
	int mid = (l+r)/2;
	down(id);
	update(2*id,l,mid,u,v,val);
	update(2*id+1,mid+1,r,u,v,val);
	if(st[2*id] == st[2*id+1]) st[id] = st[2*id];
	else st[id] = -1;
}
int lca(int u, int v){
	while(head[u] != head[v]){
		if(h[head[u]] < h[head[v]]) v = par[head[v]];
		else u = par[head[u]];
	}
	if(h[u] < h[v]) return u;
	else return v;
}
void hld(int u, int v, int val){
	int p = lca(u,v);
	while(head[u] != head[p]){
		update(1,1,n,sta[head[u]],sta[u],val);
		u = par[head[u]];
	}
	update(1,1,n,sta[p],sta[u],val);
	while(head[v] != head[p]){
		update(1,1,n,sta[head[v]],sta[v],val);
		v = par[head[v]];
	}
	update(1,1,n,sta[p],sta[v],val);
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++){
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 1; i <= m; i++) cin >> c[i];
	for(int i = 1; i <= q; i++){
		int l,r;
		cin >> l >> r;
		events[r].push_back({l,i});
	}
	pre(1,0);
	dfs(1,1);
    for(int i = 1; i <= 4*n; i++) st[i] = -1;
    for(int i = 1; i <= m; i++){
    	if(i > 1) hld(c[i-1],c[i],i-1);
    	update(1,1,n,sta[c[i]],sta[c[i]],i);
    	for(auto[l,id]: events[i]) ans[id] = get(l);
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

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