oj.uz

Submission #855194

# Submission time Handle Problem Language Result Execution time Memory
855194 2023-09-30T14:37:17 Z willychan Tourism (JOI23_tourism) C++14
7 / 100
 628 ms 19636 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
int n,m,q;
const int N = 1e5+5;
int sz[N];
int hd[N];
int dep[N];
int p[N];
vector<int> side[N];
int t;
void dfs_sz(int cur){
	sz[cur]=1;
	for(int i=0;i<side[cur].size();i++){
		if(!sz[side[cur][i]]){
			dfs_sz(side[cur][i]);
			sz[cur]+=sz[side[cur][i]];
			if(sz[side[cur][i]]>sz[side[cur][0]]){
				swap(side[cur][i],side[cur][0]);
			}
		}
	}
}
void dfs_hd(int cur){
	dep[cur]=++t;
	for(int i=0;i<side[cur].size();i++){
		if(!hd[side[cur][i]]){
			p[side[cur][i]] = cur;
			if(i==0) hd[side[cur][i]] = hd[cur];
			else hd[side[cur][i]] = side[cur][i];
			dfs_hd(side[cur][i]);
		}
	}
}

map<int,int> s;
vector<int> bit;
void modify(int ind,int v){
	if(ind==0) return;
	while(ind<=m){
		bit[ind]+=v;
		ind+=(ind&-ind);
	}
}
int Query(int ind){
	int ans = 0;
	while(ind){
		ans+=bit[ind];
		ind-=(ind&-ind);
	}
	return ans;
}
void setx(int l,int r,int x){
	auto lit = s.upper_bound(l);
	lit = prev(lit);
	int fl = lit->first;
	int fv = lit->second;
	int pv = 0;
	while(lit->first<=r){
		pv = lit->second;
		modify(lit->second,-(next(lit)->first-lit->first));	
		auto k = lit;
		++lit;
		s.erase(k);
	}
	modify(x,r-l+1);
	modify(fv,l-fl);
	if(lit->first!=r+1){
		s[r+1] = pv;
		modify(pv,lit->first-(r+1));
	}
	s[fl] = fv;
	s[l] = x;
}

void cover(int a,int b,int x){
	while(a!=b){
		if(hd[a]==hd[b]){
			int l = dep[a];
			int r = dep[b];
			if(l>r) swap(l,r);
			setx(l,r,x);
			a=b;
		}else{
			if(dep[hd[a]]>dep[hd[b]]) swap(a,b);
			int l = dep[hd[b]];
			int r = dep[b];
			setx(l,r,x);
			b = p[hd[b]];
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	bit.resize(m+1);
	s[1]=0;
	s[n+1]=0;
	for(int i=0;i<n-1;i++){
		int a,b;cin>>a>>b;
		side[a].push_back(b);
		side[b].push_back(a);
	}
	p[1]=1;
	hd[1]=1;
	dfs_sz(1);
	dfs_hd(1);
	vector<int> arr(m+1);
	for(int i=1;i<=m;i++) cin>>arr[i];
	vector<pair<int,int>> query(q);
	vector<int> ord(q);
	vector<int> ans(q);
	for(int i=0;i<q;i++){
		cin>>query[i].first>>query[i].second;
		ord[i]=i;
	}
	sort(ord.begin(),ord.end(),[&](const int a,const int b){return query[a].second<query[b].second;});
	int qhead = 0;
	for(int r=1;r<=m;r++){
		if(r>1){
			int u = arr[r-1];
			int v = arr[r];
			cover(u,v,r);
		}else{
			setx(dep[arr[r]],dep[arr[r]],1)	;
		}
		while(qhead<q && query[ord[qhead]].second==r){
			ans[ord[qhead]]=Query(m)-Query(query[ord[qhead]].first);
			qhead++;
		}
	}
	for(int i=0;i<q;i++){
		cout<<max(1,ans[i])<<"\n";
	}
	return 0;
}

Compilation message

tourism.cpp: In function 'void dfs_sz(int)':
tourism.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i=0;i<side[cur].size();i++){
      |              ~^~~~~~~~~~~~~~~~~
tourism.cpp: In function 'void dfs_hd(int)':
tourism.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i=0;i<side[cur].size();i++){
      |              ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 73 ms 11004 KB Output is correct
5 Correct 58 ms 13400 KB Output is correct
6 Correct 72 ms 16668 KB Output is correct
7 Correct 98 ms 19504 KB Output is correct
8 Correct 110 ms 19540 KB Output is correct
9 Correct 100 ms 19348 KB Output is correct
10 Correct 91 ms 19540 KB Output is correct
11 Correct 92 ms 19452 KB Output is correct
12 Correct 88 ms 19636 KB Output is correct
13 Correct 98 ms 19600 KB Output is correct
14 Correct 87 ms 19540 KB Output is correct
15 Correct 40 ms 16968 KB Output is correct
16 Correct 111 ms 18992 KB Output is correct
17 Correct 32 ms 6480 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 241 ms 8036 KB Output is correct
3 Correct 425 ms 8672 KB Output is correct
4 Correct 315 ms 10288 KB Output is correct
5 Correct 489 ms 14020 KB Output is correct
6 Correct 546 ms 14044 KB Output is correct
7 Correct 497 ms 14284 KB Output is correct
8 Correct 502 ms 13976 KB Output is correct
9 Correct 502 ms 13992 KB Output is correct
10 Correct 509 ms 14200 KB Output is correct
11 Correct 533 ms 13828 KB Output is correct
12 Correct 492 ms 13932 KB Output is correct
13 Incorrect 502 ms 14240 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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

Subtask #6
0 / 41.0

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