Submission #1317658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317658		jahongir	Tourism (JOI23_tourism)	C++20	100 / 100	430 ms	26516 KiB

tourism

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

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

#define pb push_back
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef vector<int> vi;


struct BIT{
	vector<int> bit; int n;
	void init(int _n){
		n = _n+1; bit.assign(n+5,0);
	}
	void add(int i, int val){
		for(i++; i <= n; i+=i&-i)
			bit[i] += val;
	}
	int get(int i){
		int res = 0;
		for(i++; i > 0; i-=i&-i)
			res += bit[i];
		return res;
	}
}bit;


struct Segment{
	mutable int l,r,v;
	bool operator<(const Segment &o) const {return l < o.l;}
	bool operator<(int x) const {return l < x;}
};

struct Segmento : multiset<Segment,less<>> {

	void add(int l, int r, int v){
		bit.add(v,r-l+1);
		if(!empty()){
			auto it = lower_bound(l+1);
			it--;
			if(it->l < l){
				if(it->r >= r){
					bit.add(it->v,-(r-l+1));
					int x = it->r;
					it->r = l-1;
					if(x > r) insert({r+1,x,it->v});
					it++;
				}else{
					bit.add(it->v,-(it->r-l+1));
					it->r = l-1;
					it++;
				}
			}
			while(it != end() && it->l <= r){
				if(it->r <= r){
					bit.add(it->v,-(it->r - it->l + 1));
					it = erase(it);
				}else{
					bit.add(it->v,-(r - it->l + 1));
					it->l = r+1;
					it++;
				}
			}
		}
		insert({l,r,v});
	}

}segmento;

const int mxn = 1e5+1;
vector<int> g[mxn];
int par[mxn],head[mxn],pos[mxn];
int heavy[mxn],cur_pos=0,depth[mxn];

int pre_dfs(int u = 1, int p = 0){
	int sz = 1, mx = 0; par[u] = p;
	depth[u] = depth[p]+1;
	for(auto v : g[u]) if(v!=p){
		int vsz = pre_dfs(v,u);
		sz += vsz;
		if(mx < vsz)
			heavy[u] = v, mx = vsz;
	}
	return sz;
}

void decompose(int u = 1, int h = 1){
	head[u] = h, pos[u] = ++cur_pos;
	if(heavy[u]) decompose(heavy[u],h);
	for(auto v : g[u]) if(v!=par[u] && v!=heavy[u])
		decompose(v,v);
}


void solve(){
	int n,m,q; cin >> n >> m >> q;

	for(int i = 1; i < n; i++){
		int u,v; cin >> u >> v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}

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

	vector<pii> qu[m+1];
	vector<int> res(q);
	for(int i = 0; i < q; i++){
		int l,r; cin >> l >> r;
		qu[r].emplace_back(pii{l,i});
	}

	pre_dfs();
	decompose();
	bit.init(m);
	segmento.add(1,n,0);

	for(int i = 1; i <= m; i++){
		if(i>1){
			int u = nodes[i], v = nodes[i-1];

			for(; head[u] != head[v]; v = par[head[v]]){
				if(depth[head[u]] > depth[head[v]]) swap(u,v);
				segmento.add(pos[head[v]],pos[v],i-1);
			}

			if(depth[u] > depth[v]) swap(u,v);
			segmento.add(pos[u],pos[v],i-1);
		}

		segmento.add(pos[nodes[i]],pos[nodes[i]],i);


		for(auto [l,j] : qu[i])
			res[j] = n - bit.get(l-1);
	}


	for(int i = 0; i < q; i++)
		cout << res[i] << '\n';


}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--){solve();}
}

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