Submission #1224444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224444		ByeWorld	Tourism (JOI23_tourism)	C++20	52 / 100	5092 ms	23060 KiB

tourism

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
// #define int long long
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define POP __builtin_popcount
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
const int MAXN = 1e5+10;
const int SQRT = 300;
const int INF = 1e9;
const int MOD = 1e9+7;
const int LOG = 20;
int sum(int a, int b){ a%=MOD; b%=MOD; return (a+MOD+b)%MOD; }
void chsum(int &a, int b){ a%=MOD; b%=MOD; a = (a+MOD+b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
int expo(int a, int b){
	if(b==0) return 1;
	int te = expo(a, b/2); te = mul(te,te);
	return (b%2 ? mul(te,a) : te);
}
void chmul(int &a, int b){ a = (a*b)%MOD; }
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }

int n, m, q, b[MAXN];
int dep[MAXN], anc[MAXN][LOG+5];
int tim[MAXN], day;
vector<int> adj[MAXN];

void dfs(int nw, int pa){
	dep[nw] = dep[pa]+1; anc[nw][0] = pa;
	tim[nw] = ++day;
	for(auto nx : adj[nw]){
		if(nx==pa) continue;
		dfs(nx,nw);
	}
}
int LCA(int x, int y){
	if(dep[x] > dep[y]) swap(x, y);
	for(int i=LOG-1; i>=0; i--)
		if(dep[anc[y][i]] >= dep[x]) y = anc[y][i];
	if(x==y) return x;
	for(int i=LOG-1; i>=0; i--)
		if(anc[x][i] != anc[y][i])
			x = anc[x][i], y = anc[y][i];
	return anc[x][0];
}

struct seg {
	int st[MAXN];
	int que(int x){
		int te = 0;
		for(; x; x-=x&-x) te += st[x];
		return te;
	}
	void upd(int x, int p){
		for(; x<=MAXN-10; x+=x&-x) st[x] += p;
	}
} A;
vector<pii> que[MAXN];
int mn[MAXN], ans[MAXN];

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1; i<=n-1; i++){
		int x, y; cin>>x>>y;
		adj[x].pb(y); adj[y].pb(x);
	}
	dfs(1,0);
	for(int j=1; j<LOG; j++)
		for(int i=1; i<=n; i++)
			anc[i][j] = anc[anc[i][j-1]][j-1];

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

	for(int X=1; X<=q; X++){
		int l, r; cin>>l>>r;
		if(l==r) ans[X] = 1;
		else que[l].pb({r, X});
	}
	for(int i=1; i<=n; i++) mn[i] = INF;
	for(int i=m-1; i>=1; i--){
		// upd b[i] - b[i+1]
		int lca = LCA(b[i], b[i+1]);
		int nw = b[i];
		while(nw != lca){
			if(mn[nw] != INF) A.upd(mn[nw], -1);
			mn[nw] = i; A.upd(mn[nw], 1);

			nw = anc[nw][0];
		}
		nw = b[i+1];
		while(nw != lca){
			if(mn[nw] != INF) A.upd(mn[nw], -1);
			mn[nw] = i; A.upd(mn[nw], 1);

			nw = anc[nw][0];
		}

		for(auto [r, idx] : que[i]){
			ans[idx] = A.que(r-1)+1;
		}
		// cout << i << " i\n";
		// for(int j=1; j<=n; j++) cout << mn[j] << " \n"[j==n];
	}

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

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