Submission #431323

#	Time	Username	Problem	Language	Result	Execution time	Memory
431323		MilosMilutinovic	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1370 ms	85564 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
 
const int N=200050;
const int L=20;
 
int par[N][L],lid[N],rid[N],tid,dep[N];
vector<int> E[N];
 
void DFS(int u,int p){
    par[u][0]=p;
    dep[u]=dep[p]+1;
    for(int i=1;i<L;i++)par[u][i]=par[par[u][i-1]][i-1];
    lid[u]=++tid;
    for(int v:E[u])if(v!=p)DFS(v,u);
    rid[u]=tid;
}
 
bool ancestor(int u,int v){
    return lid[u]<=lid[v]&&rid[v]<=rid[u];
}
 
int LCA(int u,int v){
    if(ancestor(u,v))return u;
    if(ancestor(v,u))return v;
    for(int i=L-1;i>=0;i--){
        if(par[u][i]>0&&!ancestor(par[u][i],v))u=par[u][i];
    }
    return par[u][0];
}
 
int n,m,q,a[N];
set<int> nodes[N][2];
void Update(int i){
    if(i<=0)return;
    nodes[a[i]][1].insert(i);
    if(i<m){
        nodes[LCA(a[i],a[i+1])][0].insert(i);
    }
}
 
void Remove(int i){
    if(i<=0)return;
    nodes[a[i]][1].erase(i);
    if(i<m){
        nodes[LCA(a[i],a[i+1])][0].erase(i);
    }
}
 
int main(){
    scanf("%i%i%i",&n,&m,&q);
    for(int i=1;i<n;i++){
        int u,v;scanf("%i%i",&u,&v);
        E[u].pb(v);
        E[v].pb(u);
    }
    for(int i=1;i<=m;i++)scanf("%i",&a[i]);
    DFS(1,0);
    for(int i=1;i<=m;i++)Update(i);
    while(q--){
        int type;scanf("%i",&type);
        if(type==1){
            int pos,v;scanf("%i%i",&pos,&v);
            Remove(pos-1);
            Remove(pos);
            a[pos]=v;
            Update(pos-1);
            Update(pos);
        }else{
            int l,r,v;scanf("%i%i%i",&l,&r,&v);
            auto x=nodes[v][0].lower_bound(l);
            auto y=nodes[v][1].lower_bound(l);
            if(x!=nodes[v][0].end()&&*x<r){
                printf("%i %i\n",*x,*x+1);
                continue;
            }
            if(y!=nodes[v][1].end()&&*y<=r){
                printf("%i %i\n",*y,*y);
                continue;
            }
            printf("-1 -1\n");
        }
    }
    return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%i%i%i",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:54:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         int u,v;scanf("%i%i",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~
treearray.cpp:58:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     for(int i=1;i<=m;i++)scanf("%i",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~
treearray.cpp:62:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         int type;scanf("%i",&type);
      |                  ~~~~~^~~~~~~~~~~~
treearray.cpp:64:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             int pos,v;scanf("%i%i",&pos,&v);
      |                       ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:71:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |             int l,r,v;scanf("%i%i%i",&l,&r,&v);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~

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