Submission #260637

#	Time	Username	Problem	Language	Result	Execution time	Memory
260637		uacoder123	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1741 ms	91204 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))

typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
vi al[200001];
set<ii> ans[200001];
int par[200001][32],din[200001],dout[200001],ti=0,n,m,q,arr[200001];
void dfs(int node,int p)
{
	par[node][0]=p;
	for(int i=1;i<32;++i)
		par[node][i]=par[par[node][i-1]][i-1];
	din[node]=ti++;
	for(int i=0;i<al[node].size();++i)
		if(al[node][i]!=p)
			dfs(al[node][i],node);
	dout[node]=ti++;
}
bool isa(int f,int s)
{
	return (din[f]<=din[s])&&(dout[f]>=dout[s]);
}
int lca(int f,int s)
{
	if(isa(f,s))
		return f;
	if(isa(s,f))
		return s;
	for(int i=31;i>=0;--i)
		if(!isa(par[f][i],s))
			f=par[f][i];
	return par[f][0];
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>n>>m>>q;
  for(int i=0;i<n-1;++i)
  {
  	int f,s;
  	cin>>f>>s;
  	al[f].pb(s);
  	al[s].pb(f);
  }
  dfs(1,1);
  for(int i=0;i<m;++i)
  	cin>>arr[i];
  for(int i=0;i<m;++i)
  {
  	ans[arr[i]].insert(mp(i,i));
  	int l;
  	if(i!=0)
  	{
  		l=lca(arr[i-1],arr[i]);
  		ans[l].insert(mp(i-1,i));
  	}
  	if(i!=m-1)
  	{
  		l=lca(arr[i+1],arr[i]);
  		ans[l].insert(mp(i,i+1));	
  	}
  }
  for(int i=0;i<q;++i)
  {
  	int t,f,s,l,v;
  	cin>>t>>f>>s;
  	if(t==1)
  	{
  		f--;
  		ans[arr[f]].erase(mp(f,f));
  		if(f!=0)
  		{
  			l=lca(arr[f-1],arr[f]);
  			ans[l].erase(mp(f-1,f));
  		}
  		if(f!=m-1)
  		{
  			l=lca(arr[f+1],arr[f]);
  			ans[l].erase(mp(f,f+1));	
  		}
  		arr[f]=s;
  		ans[s].insert(mp(f,f));
  		if(f!=0)
  		{
  			l=lca(arr[f-1],arr[f]);
  			ans[l].insert(mp(f-1,f));
  		}
  		if(f!=m-1)
  		{
  			l=lca(arr[f+1],arr[f]);
  			ans[l].insert(mp(f,f+1));	
  		}
  	}
  	else
  	{
  		f--;
  		s--;
  		cin>>v;
  		auto it=ans[v].lower_bound(mp(f,0));
  		if(it!=ans[v].end())
  		{
  			if((*it).S<=s)
  				cout<<(*it).F+1<<' '<<(*it).S+1<<endl;
  			else
  				cout<<-1<<' '<<-1<<endl;
  		}
  		else
  			cout<<-1<<' '<<-1<<endl;
  	}
  }
  return(0);
}

Compilation message (stderr)

treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:26:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<al[node].size();++i)
              ~^~~~~~~~~~~~~~~~

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