oj.uz

Submission #741739

# Submission time Handle Problem Language Result Execution time Memory
741739 2023-05-14T18:06:08 Z arnold518 Tourism (JOI23_tourism) C++17
0 / 100
 541 ms 16460 KB 
#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<=N; 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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5012 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5012 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4956 KB Output is correct
3 Correct 4 ms 5076 KB Output is correct
4 Incorrect 96 ms 16460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5016 KB Output is correct
2 Correct 211 ms 10860 KB Output is correct
3 Incorrect 322 ms 11748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5076 KB Output is correct
4 Incorrect 541 ms 14956 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 5012 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Incorrect 3 ms 4948 KB Output isn't correct
5 Halted 0 ms 0 KB -