제출 #889788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
889788		vjudge1	Tourism (JOI23_tourism)	C++17	17 / 100	2184 ms	14376 KiB

tourism

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")

using namespace __gnu_pbds;
using namespace std;

#define int long long
#define pb push_back

const int N = 1e5 + 1,INF = 1e18;

vector<int> c1(N),c2(N);
vector<int> g[N];
pair<int,int> t[N * 4];
 
void build(int tl,int tr,int v){
	if(tl == tr){
		t[v].first = c1[tl];
		t[v].second = c1[tl];
		return;
	}
	int tm = (tl + tr) >> 1;
	build(tl,tm,v * 2);
	build(tm + 1,tr,v * 2 + 1);
	t[v].first = max(t[v * 2].first,t[v * 2 + 1].first);
	t[v].second = min(t[v * 2].second,t[v * 2 + 1].second);
}
 
pair<int,int> get(int l,int r,int v,int tl,int tr){
	if(tl > r || tr < l){
		return {-INF,INF};
	}
	if(l <= tl && tr <= r){
		return t[v];
	}
	int tm = (tl + tr) >> 1;
	pair<int,int> x,y;
	x = get(l, r, v * 2,tl,tm);
	y = get(l,r,v * 2 + 1,tm + 1,tr);
	pair<int,int> res;
	res.first = max(x.first,y.first);
	res.second = min(x.second,y.second);
	return res;
}
 
void solve(){
	
	int n,q,m;
	cin >> n >> m >> q;
	
	for(int i = 0;i < n - 1;i++){
		int a,b;
		cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	
	for(int i = 1;i <= m;i++){
		int a;
		cin>>a;
		c1[i] = a;
		c2[a] = i;
	}
	if(n <= 2000){
		while(q--){
			int l,r;
			cin >> l >> r;
			vector<int> dis(n + 1);
			queue<pair<int,int>> q;
			q.push({c1[l],-1});
			dis[c1[l]] = 1;
			vector<int> pr(n + 1);
			while(!q.empty()){
				auto [v,p] = q.front();
				q.pop();
				
				for(auto u : g[v]){
					if(u != p){
						dis[u] = dis[v] + 1;
						pr[u] = v;
						q.push({u,v});
					}
				}
			}
			vector<int> ans(n + 1);
			for(int i = l + 1;i <= r;i++){
				int y = c1[i];
				while(y != c1[l] && !ans[y]){
					ans[y] = 1;
					y = pr[y];
				}
			}
			int cnt = 0;
			for(int i = 1;i <= n;i++){
				cnt += ans[i];
			}
			cout<<cnt + 1<<"\n";
			
			
		}
	
	}
	else{
		build(1,m,1);
		while(q--){
			int l,r;
			cin >> l >> r;
			auto [ans1,ans2] = get(l,r,1,1,m);
			cout << ans1 - ans2 + 1 << "\n";
		}
	}
 
}
 
signed main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
 
}

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