oj.uz

Submission #85340

# Submission time Handle Problem Language Result Execution time Memory
85340 2018-11-19T11:31:57 Z ToadDaveski Birthday gift (IZhO18_treearray) C++14
0 / 100
 24 ms 24056 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector <ll> v[200001];
ll p[32][200001],tin[200001],tout[200001],a[200001],timer;
bool isA(ll x,ll y)
{
    if (tin[x]<=tin[y] && tout[x]>=tout[y])
        return true;
    return false;
}
void dfs(ll x,ll pr)
{
    tin[x]=++timer;
    p[0][x]=pr;
    for(ll i=1;i<=30;i++)
        p[i][x]=p[i-1][p[i-1][x]];
    for(ll to : v[x])
        if (to!=pr)
             dfs(to,x);
    tout[x]=++timer;
}
ll lca(ll x,ll y)
{
    if (isA(x,y))
        return x;
    if (isA(y,x))
        return y;
    while(!isA(p[0][x],y))
    {
        ll i;
        for(i=30;i>=0;i--)
            if (!isA(p[i][x],y)) break;
        x=p[i][x];
    }
    return p[0][x];
}
set <ll> ans[200001],answ[200001];
set <ll > :: iterator it;
int main()
{
    ll n,m,q,i,j;
    cin>>n>>m>>q;
    for(i=1;i<=n-1;i++)
    {
        ll x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,1);
    for(i=1;i<=m;i++)
        cin>>a[i];
    for(i=1;i<m;i++)
    {
        answ[a[i]].insert(i);
        ans[lca(a[i],a[i+1])].insert(i);
    }
    answ[a[m]].insert({m,m});
    for(i=1;i<=q;i++)
    {
        ll type;
        cin>>type;
        if (type==1)
        {
            ll x,y;
            cin>>x>>y;
            answ[a[x]].erase(x);
            if (x!=m) ans[lca(a[x],a[x+1])].erase(x);
            answ[y].insert(x);
            if (x!=m) ans[lca(y,a[x+1])].insert(x);
            a[x]=y;
        }
        else
        {
            ll l,r,x;
            cin>>l>>r>>x;
            it=ans[x].lower_bound(l);
            if (it!=ans[x].end() && (*it)+1<=r)
            {
                cout<<(*it)<<" "<<(*it)+1<<endl;
                continue;
            }
            it=answ[x].lower_bound(l);
            if (it!=answ[x].end() && (*it)<=r)
            {
                cout<<(*it)<<" "<<(*it)<<endl;
                continue;
            }
            cout<<-1<<" "<<-1<<endl;
        }
    }
    return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:42:16: warning: unused variable 'j' [-Wunused-variable]
     ll n,m,q,i,j;
                ^

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 24056 KB Wrong range.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 24056 KB Wrong range.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 24056 KB Wrong range.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 24056 KB Wrong range.
2 Halted 0 ms 0 KB -