Submission #342704

#	Time	Username	Problem	Language	Result	Execution time	Memory
342704		David_M	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1482 ms	118320 KiB

treearray

#include <bits/stdc++.h> 
#define ll long long
#define F first
#define S second
#define FF first.first
#define FS first.second
#define pb push_back
using namespace std;
const ll N=200006, INF=1e18;
     
ll pos, l, r, n, m, t, a[N], b[N], h[N], p[20][N], q, k, x, y;
vector <ll> v[N];
set <ll> s[N], S[N];

void build(){
    for (int i=1; i<=19; i++)
        for (int j=1; j<=n; j++)
        	p[i][j]=-1;
        	
	for (int i=1; i<=19; i++)
		for (int j=1; j<=n; j++)
			if(p[i-1][j]!=-1) p[i][j]=p[i-1][p[i-1][j]];
}  

void dfs(int x, int pa){
	s[x].insert(INF),
	S[x].insert(INF);
	p[0][x]=pa;
	for (int i=0; i<v[x].size(); i++){
		int y=v[x][i];
		if(y==pa)continue;
		h[y]=h[x]+1;
		dfs(y, x);
	}
}

int lca(int x, int y){
	if(h[y]<h[x])swap(x, y);
	int l=h[y]-h[x];
	
	for (int i=19; i>=0; i--) if((l>>i)&1)y=p[i][y];
	if(x==y)return x;
	
	for (int i=19; i>=0; i--) if(p[i][x]!=p[i][y])x=p[i][x],y=p[i][y];
	return p[0][x];
}

int main(){ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n>>m>>q;
	
	for (int i=1; i<n; i++)
		cin>>x>>y,
		v[x].pb(y),
		v[y].pb(x);
	
	dfs(1, 1);
	build();
	
	for (int i=1; i<=m; i++){
		cin>>a[i];
		S[a[i]].insert(i);
		if(i==1)continue;
		k=lca(a[i], a[i-1]);
		b[i]=k;
		s[k].insert(i);
	}
	
	while(q--){
		cin>>t;
		if(t==1){
			cin>>pos>>x;
			if(pos>1)s[b[pos]].erase(pos);
			if(pos<m)s[b[pos+1]].erase(pos+1);
			S[a[pos]].erase(pos);
			a[pos]=x;
			S[a[pos]].insert(pos);
			if(pos>1)k=lca(a[pos], a[pos-1]), b[pos]=k,  s[k].insert(pos);
			if(pos<m)k=lca(a[pos], a[pos+1]), b[pos+1]=k,s[k].insert(pos+1);
		}else{
			cin>>l>>r>>x;
			k=*(s[x].upper_bound(l));
			if(k<=r)cout<<k-1<<" "<<k<<'\n';
			else{
				k=*(S[x].lower_bound(l));
				if(k<=r)cout<<k<<" "<<k<<'\n';
				else cout<<"-1 -1\n";
			}
		}
	}
	
}

Compilation message (stderr)

treearray.cpp: In function 'void build()':
treearray.cpp:16:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   16 |     for (int i=1; i<=19; i++)
      |     ^~~
treearray.cpp:20:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   20 |  for (int i=1; i<=19; i++)
      |  ^~~
treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (int i=0; i<v[x].size(); i++){
      |                ~^~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44