Submission #1029841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029841		Unforgettablepl	Tourism (JOI23_tourism)	C++17	28 / 100	5042 ms	34132 KiB

tourism

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

#define int long long

const int INF = 1e18;

struct segtree{
	vector<int> tree;
	segtree():tree(262144){}
	void update(int k,int x){
		k+=131072;
		tree[k]=x;
		while(k/=2){
			tree[k]=min(tree[2*k],tree[2*k+1]);
		}
	}
	int get(int a,int b){
		a+=131072;b+=131072;
		int ans = INF;
		while(a<=b){
			if(a&1)ans=min(ans,tree[a++]);
			if(b%2 == 0)ans=min(ans,tree[b--]);
			a/=2;b/=2;
		}
		return ans;
	}
};

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);
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	int tim = 0;
	vector<int> newidx(n+1);
	function<void(int,int)> dfs = [&](int x,int par){
		newidx[x]=++tim;
		for(int&i:adj[x])if(i!=par)dfs(i,x);
	};
	dfs(1,0);
	vector<vector<int>> newadj(n+1);
	for(int i=1;i<=n;i++)newadj[newidx[i]]=adj[i];
	for(int i=1;i<=n;i++){
		for(int&x:newadj[i])x=newidx[x];
	}
	swap(newadj,adj);
	vector<vector<int>> lift(n+1,vector<int>(17));
	vector<int> depth(n+1);
	function<void(int,int,int)> dfs2 = [&](int x,int par,int dep){
		lift[x][0]=par;
		depth[x]=dep;
		for(int&i:adj[x])if(i!=par)dfs2(i,x,dep+1);
	};
	dfs2(1,0,1);
	for(int bit=1;bit<17;bit++){
		for(int i=1;i<=n;i++){
			lift[i][bit] = lift[lift[i][bit-1]][bit-1];
		}
	}
	auto lca = [&](int a,int b){
		if(depth[a]>depth[b])swap(a,b);
		int tar = depth[b]-depth[a];
		for(int bit=0;bit<17;bit++)if(tar&(1<<bit))b=lift[b][bit];
		if(a==b)return a;
		for(int bit=16;bit>=0;bit--){
			if(lift[a][bit]!=lift[b][bit]){
				a = lift[a][bit];
				b = lift[b][bit];
			}
		}
		return lift[a][0];
	};
	vector<int> checkpoints(m+1);
	for(int i=1;i<=m;i++){
		int x;cin>>x;
		checkpoints[i]=newidx[x];
	}
	for(int i=1;i<=q;i++){
		int l,r;
		cin >> l >> r;
		vector<int> buffer;
		for(int x=l;x<=r;x++)buffer.emplace_back(checkpoints[x]);
		sort(buffer.begin(),buffer.end());
		int lcaall = buffer[0];
		for(int&x:buffer)lcaall=lca(lcaall,x);
		int ans = depth[buffer[0]]-depth[lcaall]+1;
		for(int x=1;x<buffer.size();x++){
			ans+=depth[buffer[x]]-depth[lca(buffer[x],buffer[x-1])];
		}
		cout << ans << '\n';
	}
}

Compilation message (stderr)

tourism.cpp: In function 'int32_t main()':
tourism.cpp:94:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for(int x=1;x<buffer.size();x++){
      |               ~^~~~~~~~~~~~~~

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