This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define MAXN 200010
#define logn 18
using namespace std;
vector<ll> G[MAXN];
set<ll> poslca[MAXN],posv[MAXN];
ll a[MAXN],up[MAXN][logn],in[MAXN],out[MAXN],t;
void DFS(ll i,ll p)
{
in[i]=t++;
up[i][0]=p;
for (ll j=1;j<logn;j++)
up[i][j]=up[up[i][j-1]][j-1];
for (ll next : G[i])
{
if (next!=p)
DFS(next,i);
}
out[i]=t++;
}
bool Is_Ancestor(ll u,ll v)
{
return in[u]<=in[v] && out[u]>=out[v];
}
ll LCA(ll u,ll v)
{
if (Is_Ancestor(u,v))
return u;
if (Is_Ancestor(v,u))
return v;
for (ll i=logn-1;i>=0;i--)
{
if (!Is_Ancestor(up[u][i],v))
u=up[u][i];
}
return up[u][0];
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n,m,q,u,v,type,pos,l,r;
cin >> n >> m >> q;
for (ll i=1;i<n;i++)
{
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
DFS(1,1);
for (ll i=1;i<=m;i++)
{
cin >> a[i];
if (i>1)
poslca[LCA(a[i-1],a[i])].insert(i-1);
posv[a[i]].insert(i);
}
while (q--)
{
cin >> type;
if (type==1)
{
cin >> pos >> v;
if (pos>1)
{
poslca[LCA(a[pos-1],a[pos])].erase(pos-1);
poslca[LCA(a[pos-1],v)].insert(pos-1);
}
if (pos<m)
{
poslca[LCA(a[pos],a[pos+1])].erase(pos);
poslca[LCA(v,a[pos+1])].insert(pos);
}
posv[a[pos]].erase(pos);
posv[v].insert(pos);
a[pos]=v;
continue;
}
cin >> l >> r >> v;
auto it=posv[v].lower_bound(l);
if (it!=posv[v].end() && *it<=r)
{
cout << *it << " " << *it << "\n";
continue;
}
it=poslca[v].lower_bound(l);
if (it==poslca[v].end() || *it>=r)
cout << -1 << " " << -1 << "\n";
else
cout << *it << " " << *it+1 << "\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |