Submission #741741

#	Time	Username	Problem	Language	Result	Execution time	Memory
741741		arnold518	Tourism (JOI23_tourism)	C++17	100 / 100	728 ms	24420 KiB

tourism

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, M, Q;
vector<int> adj[MAXN+10];
int A[MAXN+10], ans[MAXN+10];
vector<pii> B[MAXN+10];


int sz[MAXN+10], par[MAXN+10], dep[MAXN+10];
void dfs(int now, int bef, int d)
{
	sz[now]=1;
	par[now]=bef;
	dep[now]=d;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
		sz[now]+=sz[nxt];
	}
}

int dfn[MAXN+10], head[MAXN+10], cnt;
void hld(int now, int bef)
{
	dfn[now]=++cnt;
	int heavy=0;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(sz[heavy]<sz[nxt]) heavy=nxt;
	}

	if(heavy==0) return;

	head[heavy]=head[now];
	hld(heavy, now);
	for(int nxt : adj[now])
	{
		if(nxt==bef || nxt==heavy) continue;
		head[nxt]=nxt;
		hld(nxt, now);
	}
}

struct BIT
{
	int tree[MAXN+10];
	void update(int i, int k) { for(; i<=M; i+=(i&-i)) tree[i]+=k; }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
}bit;

set<pair<pii, int>> S;

void update(int l, int r, int k)
{
	//printf("%d %d %d\n", l, r, k);
	auto it=S.lower_bound({{l, 0}, 0});
	if(it!=S.begin() && prev(it)->first.second>=l) it--;
	vector<pair<pii, int>> V;
	for(; it!=S.end() && it->first.first<=r;)
	{
		int l2=it->first.first, r2=it->first.second, v=it->second;
		if(l2<l) V.push_back({{l2, l-1}, v});
		if(r<r2) V.push_back({{r+1, r2}, v});
		it=S.erase(it);
		bit.update(v, -(r2-l2+1));
	}
	for(auto it : V) S.insert(it), bit.update(it.second, it.first.second-it.first.first+1);
	S.insert({{l, r}, k}); bit.update(k, r-l+1);
	
	//for(auto it : S) printf("(%d %d %d) ", it.first.first, it.first.second, it.second); printf("\n");
}

void query(int u, int v, int k)
{
	while(head[u]!=head[v])
	{
		if(dep[head[u]]>dep[head[v]]) swap(u, v);
		update(dfn[head[v]], dfn[v], k);
		v=par[head[v]];
	}
	if(dep[u]>dep[v]) swap(u, v);
	update(dfn[u], dfn[v], k);
}

int main()
{
	scanf("%d%d%d", &N, &M, &Q);
	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1; i<=M; i++) scanf("%d", &A[i]);
	for(int i=1; i<=Q; i++)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		B[r].push_back({l, i});
	}

	dfs(1, 1, 1);
	head[1]=1;
	hld(1, 1);

	for(int i=1; i<=M; i++)
	{
		for(auto it : B[i])
		{
			ans[it.second]=bit.query(M)-bit.query(it.first-1);
		}
		if(i+1<=M) query(A[i], A[i+1], i);
	}
	for(int i=1; i<=Q; i++) printf("%d\n", max(1, ans[i]));
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |  scanf("%d%d%d", &N, &M, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:100:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
tourism.cpp:104:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |  for(int i=1; i<=M; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~
tourism.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |   scanf("%d%d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~

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