Submission #790684

#	Time	Username	Problem	Language	Result	Execution time	Memory
790684		qwerasdfzxcl	Tourism (JOI23_tourism)	C++17	100 / 100	995 ms	20980 KiB

tourism

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9 + 100;

vector<int> adj[100100];
int a[100100], ans[100100];

int dep[100100], par[100100], sz[100100], top[100100], in[100100], out[100100], cnt;

struct Seg{
	int tree[200200], sz;
	void init(int n){
		sz = n;
		fill(tree, tree+sz*2, 0);
	}

	void update(int p, int x){
		p += sz;
		tree[p] += x;

		for (p>>=1;p;p>>=1) tree[p] = tree[p<<1] + tree[p<<1|1];
	}

	int query(int l, int r){
		++r;
		int ret = 0;
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1) ret += tree[l++];
			if (r&1) ret += tree[--r];
		}

		return ret;
	}
};

struct DS{
	set<array<int, 3>> st;
	Seg tree;

	void init(int n, int m){
		st.insert({1, n, m+1});

		tree.init(m+2);
		tree.update(m+1, n);
	}

	set<array<int, 3>>::iterator find(int x){
		return prev(st.lower_bound(array<int, 3>{x, INF, INF}));
	}

	void cut(int x){ // cut between x and x+1
		if (x < 1) return;

		auto iter = find(x);
		auto [l, r, v] = *iter;
		if (r==x) return;

		st.erase(iter);
		st.insert({l, x, v});
		st.insert({x+1, r, v});
	}

	void update(int l, int r, int x){
		// printf("update %d %d %d\n", l, r, x);
		cut(l-1);
		cut(r);

		for (auto iter=find(l);iter!=st.end();iter=st.erase(iter)){
			auto [_l, _r, _v] = *iter;
			if (_r > r) break;
			
			tree.update(_v, -(_r-_l+1));
		}

		st.insert({l, r, x});
		tree.update(x, r-l+1);

		// for (auto &[x, y, z]:st) printf("(%d, %d, %d) ", x, y, z);
		// printf("\n");
	}

	int query(int x){
		return tree.query(0, x-1);
	}
}D;

void dfs1(int s, int pa = 0){
	dep[s] = dep[pa] + 1;
	sz[s] = 1;
	par[s] = pa;

	if (pa) adj[s].erase(find(adj[s].begin(), adj[s].end(), pa));
	else top[s] = s;

	for (auto &v:adj[s]){
		dfs1(v, s);
		sz[s] += sz[v];
	}
}

void dfs2(int s){
	in[s] = ++cnt;
	sort(adj[s].begin(), adj[s].end(), [&](int i, int j){return sz[i] > sz[j];});

	for (auto &v:adj[s]){
		if (v==adj[s][0]) top[v] = top[s];
		else top[v] = v;

		dfs2(v);
	}

	out[s] = cnt;
}

void update(int x, int y, int val){
	while(top[x] != top[y]){
		if (dep[top[x]] > dep[top[y]]) swap(x, y);
		D.update(in[top[y]], in[y], val);

		y = par[top[y]];
	}

	if (dep[x] > dep[y]) swap(x, y);
	if (x!=y) D.update(in[x]+1, in[y], val);
}

int main(){
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);

	for (int i=1;i<=n-1;i++){
		int x, y;
		scanf("%d %d", &x, &y);
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	dfs1(1);
	dfs2(1);

	for (int i=1;i<=m;i++) scanf("%d", a+i);

	vector<array<int, 3>> Q;
	for (int i=1;i<=q;i++){
		int x, y;
		scanf("%d %d", &x, &y);
		Q.push_back({x, y, i});
	}

	D.init(n, m);
	sort(Q.begin(), Q.end(), greater<array<int, 3>>());

	int pt = 0;
	for (int i=m;i;i--){
		if (i<m) update(a[i], a[i+1], i);
		
		while(pt<(int)Q.size() && Q[pt][0]==i){
			ans[Q[pt][2]] = D.query(Q[pt][1]) + 1;
			pt++;
		}
	}

	for (int i=1;i<=q;i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:131:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~
tourism.cpp:143:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |  for (int i=1;i<=m;i++) scanf("%d", a+i);
      |                         ~~~~~^~~~~~~~~~~
tourism.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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