Submission #748942

#	Time	Username	Problem	Language	Result	Execution time	Memory
748942		ETheBest3	Birthday gift (IZhO18_treearray)	C++14	100 / 100	2084 ms	113864 KiB

treearray

#include<bits/stdc++.h>
#define lli long long
#define endl "\n"
using namespace std;
const lli MAXN=200005, LOGN=25;
lli N, M, Q, a[MAXN], up[LOGN][MAXN], vh1, vh2, vh3, dep[MAXN], used[MAXN], type;
vector<lli> v[MAXN];
set<lli> pos1[MAXN], pos2[MAXN];
void dfs(lli vr){
    used[vr]=1;
    for(lli i=0; i<v[vr].size(); i++){
        if(used[v[vr][i]])continue;
        up[0][v[vr][i]]=vr;
        dep[v[vr][i]]=dep[vr]+1;
        dfs(v[vr][i]);
    }
    return;
}
lli lca(lli x, lli y){
    if(dep[x]<dep[y])swap(x, y);
    for(lli i=LOGN-1; i>=0; i--){
        if(dep[x]-(1<<i)>=dep[y]){
            x=up[i][x];
        }
    }
    if(x==y)return x;
    for(lli i=LOGN-1; i>=0; i--){
        if(up[i][x]!=up[i][y]){
            x=up[i][x];
            y=up[i][y];
        }
    }
    return up[0][x];
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M>>Q;
    for(lli i=0; i<N-1; i++){
        cin>>vh1>>vh2;
        v[vh1].push_back(vh2);
        v[vh2].push_back(vh1);
    }
    dep[1]=1;
    dfs(1);
    for(lli st=1; st<LOGN; st++){
        for(lli i=1; i<=N; i++){
            up[st][i]=up[st-1][up[st-1][i]];
        }
    }
    for(lli i=1; i<=M; i++)cin>>a[i];
    for(lli i=1; i<=M; i++){
        pos1[a[i]].insert(i);
        if(i!=M)pos2[lca(a[i], a[i+1])].insert(i);
    }
    for(lli q=0; q<Q; q++){
        cin>>type;
        if(type==1){
            cin>>vh1>>vh2;
            pos1[a[vh1]].erase(vh1);
            if(vh1!=1)pos2[lca(a[vh1-1], a[vh1])].erase(vh1-1);
            if(vh1!=M)pos2[lca(a[vh1], a[vh1+1])].erase(vh1);
            a[vh1]=vh2;
            pos1[a[vh1]].insert(vh1);
            if(vh1!=1)pos2[lca(a[vh1-1], a[vh1])].insert(vh1-1);
            if(vh1!=M)pos2[lca(a[vh1], a[vh1+1])].insert(vh1);
        }else{
            cin>>vh1>>vh2>>vh3;
            auto it1=pos1[vh3].lower_bound(vh1), it2=pos2[vh3].lower_bound(vh1);
            if(it1!=pos1[vh3].end() and (*it1)<=vh2){
                cout<<(*it1)<<" "<<(*it1)<<endl;
                continue;
            }
            if(it2!=pos2[vh3].end() and (*it2)+1<=vh2){
                cout<<(*it2)<<" "<<(*it2)+1<<endl;
                continue;
            }
            cout<<"-1 -1"<<endl;
        }
    }
    return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'void dfs(long long int)':
treearray.cpp:11:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(lli i=0; i<v[vr].size(); i++){
      |                  ~^~~~~~~~~~~~~

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