Submission #342672

#	Time	Username	Problem	Language	Result	Execution time	Memory
342672		David_M	Birthday gift (IZhO18_treearray)	C++14	0 / 100	68 ms	117996 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=1000006, INF=1e18, MOD=1e9+7;
     
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++)
            if (p[i][j-1]!=-1) 
                p[i][j]=p[p[i][j-1]][j-1]; 
}  

void dfs(int x, int pa){
	for (int i=0; i<v[x].size(); i++){
		int y=v[x][i];
		if(y==pa)continue;
		h[y]=h[x]+1;
		p[0][y]=x;
		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];
//	cout<<"aaa"<<h[x]<<" "<<h[y]<<'\n';
	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<=19; i++)
        for (int j=1; j<=n; j++)
        	p[i][j]=-1;
	
	for (int i=1; i<n; i++)
		cin>>x>>y,
		v[x].pb(y),
		v[y].pb(x),
		s[i].insert(INF),
		S[i].insert(INF);
	
	s[n].insert(INF);
	S[n].insert(INF);
	p[0][1]=1;
	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]);
//		cout<<"__"<<a[i-1]<<" "<<a[i]<<" "<<k<<'\n';
		b[i]=k;
		s[k].insert(i);
	}
//	for (int i=1; i<=m; i++)cout<<b[i]<<" ";cout<<'\n';
	while(q--){
		cin>>t;
		if(t==1){
			cin>>pos>>x;
			if(pos>1)s[b[pos]].erase(pos);
			if(pos<n)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<n)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));
//			cout<<"______"<<l<<" "<<k<<'\n';
			if(k<=r)cout<<k-1<<" "<<k<<'\n';
			else{
				k=*(S[x].lower_bound(l));
//				cout<<endl<<S[x].size()<<endl;
				if(k<=r)cout<<k<<" "<<k<<'\n';
				else cout<<"-1 -1\n";
			}
		}
//		for (int i=1; i<=m; i++)cout<<b[i]<<" ";cout<<'\n';
	}
	
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

Compilation message (stderr)

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

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