Submission #1034266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034266		Unforgettablepl	Tourism (JOI23_tourism)	C++17	100 / 100	760 ms	37004 KiB

tourism

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct fenwick{
	int n;vector<int> tree;
	fenwick(int n):n(n),tree(n+1){}
	int get(int k){
		int ans = 0;
		while(k){
			ans+=tree[k];
			k-=k&-k;
		}
		return ans;
	}
	void add(int k,int x){
		while(k<=n){
			tree[k]+=x;
			k+=k&-k;
		}
	}
};

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,q;
	cin >> n >> m >> q;
	vector<vector<int>> adj(n+1);
	vector<vector<int>> nadj(n+1);
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	vector<int> tim(n+1);
	vector<int> siz(n+1);
	int c = 0;
	vector<int> next(n+1);
	vector<int> p(n+1);
	function<int(int,int)> dfs1 = [&](int x,int par){
		p[x]=par;
		siz[x]=1;
		for(int&i:adj[x])if(i!=par){
			nadj[x].emplace_back(i);
			siz[x]+=dfs1(i,x);
		}
		for(int&i:nadj[x])if(siz[i]>siz[nadj[x][0]])swap(i,nadj[x][0]);
		return siz[x];
	};
	dfs1(1,1);
	swap(nadj,adj);
	function<void(int)> dfs2 = [&](int x){
		tim[x] = ++c;
		for(int&i:adj[x]){
			if(i==adj[x][0])next[i]=next[x];
			else next[i]=i;
			dfs2(i);
		}
	};
	dfs2(1);
	map<int,int> mp;
	fenwick cnt(m+1);
	auto traverse_path = [&](int a,int b,int x){
		if(a==b)return;
		vector<pair<int,int>> paths;
		while(true){
			if(tim[a]>tim[b])swap(a,b);
			if(next[a]==next[b]){
				paths.emplace_back(tim[a]+1,tim[b]);
				break;
			}
			paths.emplace_back(tim[next[b]],tim[b]);
			b = p[next[b]];
		}
		for(auto [l,r]:paths){
			r++;
			if(l==r)continue;
			for(int y : {l,r}){
				if(mp.count(y)==0){
					auto itr = mp.lower_bound(y);
					itr--;
					mp[y]=itr->second;
				}
			}
			while(true){
				auto itr = mp.lower_bound(l);
				if(itr->first==r)break;
				auto nxt = std::next(itr);
				cnt.add(itr->second,(itr->first)-(nxt->first));
				mp.erase(itr);
			}
			mp[l]=x;
			cnt.add(x,r-l);
		}
	};
	vector<int> checkpoints(m+1);
	for(int i=1;i<=m;i++)cin>>checkpoints[i];
	vector<int> L(q),R(q);
	vector<vector<int>> queries(m+1);
	vector<int> ans(q);
	for(int i=0;i<q;i++){
		cin >> L[i] >> R[i];
		if(L[i]!=m)queries[L[i]].emplace_back(i);
	}
	cnt.add(m,n);
	mp[0]=-1;
	mp[1]=m;
	mp[n+1]=-1;
	for(int l=m-1;l;l--){
		traverse_path(checkpoints[l],checkpoints[l+1],l);
		for(int&idx:queries[l]){
			ans[idx] = cnt.get(R[idx]-1);
		}
	}
	for(int&i:ans)cout<<i+1<<'\n';
}

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