Submission #882562

#	Time	Username	Problem	Language	Result	Execution time	Memory
882562		NintsiChkhaidze	Tourism (JOI23_tourism)	C++17	28 / 100	5079 ms	56284 KiB

tourism

#include <bits/stdc++.h>
#define s second
#define f first
#define ll long long
#define pb push_back
#define pii pair <int,int>
#define int ll
using namespace std;

const int N = 2e5 + 5,inf = 1e18;

int dp[N],d[25][N],arr[N],fix[N];
int L[N],R[N],ans[N];
vector <int> v[N],qr[N];

void dfs(int x,int par){
	d[0][x] = par;
	dp[x] = dp[par] + 1;
	for (int to: v[x]){
		if (to != par){
			dfs(to,x);
		}
	}
}

int lca(int x,int y){
	if (dp[x] < dp[y]) swap(x,y);
	for (int i = 18; i >= 0; i--)
		if (dp[d[i][x]] >= dp[y]) x = d[i][x];

	if (x == y) return x;

	for (int i = 18; i >= 0; i--)
		if (d[i][x] != d[i][y]) x = d[i][x], y = d[i][y];

	return d[0][x];
}

void markpath(int x,int y,int color){
	int c = lca(x,y);
	while (x != c){
		fix[x] = color;
		x = d[0][x];
	}

	while (y != c){
		fix[y] = color;
		y = d[0][y];
	}

	fix[c] = color;
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,m,q;
	cin>>n>>m>>q;

	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}

	dfs(1,1);
	for (int j = 1; j <= 18; j++)
		for (int i = 1; i <= n; i++)
			d[j][i] = d[j - 1][d[j - 1][i]];

	for (int i = 1; i <= m; i++)
		cin >> arr[i];

	for (int i = 1; i <= q; i++){
		cin >> L[i] >> R[i];
		if (L[i] == R[i]) ans[i] = 1;
		else qr[L[i]].pb(i);
	}

	for (int i = 1; i <= n; i++)
		fix[i] = m + 1;
	
	//neli 
	for (int i = m; i >= 1; i--){
		if (i != m) markpath(arr[i],arr[i + 1],i + 1);
		for (int id: qr[i]){
			int r = R[id];
			for (int j = 1; j <= n; j++)
				ans[id] += (fix[j] <= r);
		}
	}

	for (int i = 1; i <= q; i++)	
		cout<<ans[i]<<endl;
}

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