Submission #889689

#	Time	Username	Problem	Language	Result	Execution time	Memory
889689		vjudge1	Tourism (JOI23_tourism)	C++17	0 / 100	5070 ms	10752 KiB

tourism

#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
  tomorrow will worse
  but the day after tomorrow will be the sunshine..
 
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up  */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const int N = 2e5+50, inf = 1e18, mod = 1e9+7;
vi g[N];
//~ set<pii> mp, jol;
set<int> chk;
//~ void dfs(int pos, int pr){
	//~ if(chk.empty())return;
	//~ if(chk.count(pos) > 0){
		//~ chk.erase(chk.find(pos));
		//~ vii tod;
		//~ if(!jol.empty()){
			//~ for(auto i:jol){
				//~ mp.insert(i);
				//~ tod.pb(i);
			//~ }
			//~ for(auto i:tod)jol.erase(i);
			//~ tod.clear();
		//~ }
	//~ }
	//~ for(auto to:g[pos]){
		//~ if(to == pr)continue;
		//~ jol.insert({pos, to});
		//~ dfs(to, pos);
		//~ jol.erase(jol.find({pos, to}));
	//~ }
//~ }
void solve(){
	int n, m, q, a, b;
	cin >> n >> m >> q;
	for(int i = 0; i < n-1; i++){
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	int pl[m+1]{};
	for(int i = 1; i <= m; i++){
		cin >> pl[i];
	}
	while(q--){
		int l, r, ans = 0;
		cin >> l >> r;
		for(int i = l+1; i <= r; i++)chk.insert(pl[i]);
		//~ dfs(pl[l], -1);
		//~ cout << mp.size()+1 << '\n';
		//~ mp.clear();
		queue<pii> q;
		q.push({pl[l], 0});
		int us[n+1]{};
		while(!q.empty()){
			auto [pos, ds] = q.front();
			//~ cout << pos << ' ' << ds << '\n';
			q.pop();
			us[pos] = 1;
			for(auto to:g[pos]){
				if(us[to])continue;
				if(chk.count(to)){
					ans += ds+1;
					ds = 0;
				}
			}
			for(auto to:g[pos]){
				if(us[to])continue;
				
				if(chk.count(to)){
					chk.erase(to);
					q.push({to, 0});
				}else q.push({to, ds+1});
			}
			if(chk.empty())break;
		}
		cout << ans+1 << '\n';
	}
}
main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

tourism.cpp:92:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   92 | main(){
      | ^~~~

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