Submission #341701

#	Time	Username	Problem	Language	Result	Execution time	Memory
341701		ivan_tudor	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1650 ms	87448 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
const int N = 2*1e5 + 5;
vector<int> gr[N];
int par[18][N];
int in[N], out[N];
void dfs(int nod, int dad, int &cnt){
  par[0][nod] = dad;
  in[nod]= ++cnt;
  for(auto x :gr[nod]){
    if(x!=dad)
      dfs(x, nod, cnt);
  }
  out[nod] = cnt;
}
bool is_dad(int dad, int nod){
  if(in[dad]<= in[nod] && out[nod]<= out[dad])
    return true;
  return false;
}
int get_lca(int a,int b){
  for(int log = 17; log>=0; log--){
    if(par[log][a]!=0 && is_dad(par[log][a], b)== false)
      a = par[log][a];
  }
  if(is_dad(a, b) == false)
    a = par[0][a];
  return a;
}
int v[N];
int lc[N];
set<int> pzv[N];
set<int> pzl[N];
int query(set<int> &pz, int l,int r){
  auto it = pz.lower_bound(l);
  if(it==pz.end())
    return -1;
  if((*it) <=r)
    return (*it);
  return -1;
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n, m, q;
  cin>>n>>m>>q;
  for(int i=1;i<n;i++){
    int a, b;
    cin>>a>>b;
    gr[a].push_back(b);
    gr[b].push_back(a);
  }
  int cnt =0;
  dfs(1, 0, cnt);
  for(int log =1 ; log < 18; log ++){
    for(int nod = 1; nod<=n;nod++){
      par[log][nod] = par[log-1][par[log-1][nod]];
    }
  }
  for(int i=1;i<=m;i++){
    cin>>v[i];
    pzv[v[i]].insert(i);
  }
  for(int i=1;i<m;i++){
    lc[i] = get_lca(v[i], v[i+1]);
    pzl[lc[i]].insert(i);
  }
  for(int i=1;i<=q;i++){
    int tip;
    cin>>tip;
    if(tip == 1){
      int poz, val;
      cin>>poz>>val;
      pzv[v[poz]].erase(poz);
      if(poz < m)
        pzl[lc[poz]].erase(poz);
      if(poz > 1)
        pzl[lc[poz-1]].erase(poz - 1);

      v[poz] = val;
      pzv[v[poz]].insert(poz);
      if(poz < m){
        lc[poz] = get_lca(v[poz], v[poz + 1]);
        pzl[lc[poz]].insert(poz);
      }
      if(poz > 1){
        lc[poz-1] = get_lca(v[poz-1], v[poz]);
        pzl[lc[poz-1]].insert(poz -1);
      }
    }
    else {
      int val, l , r;
      cin>>l>>r>>val;
      int ans = query(pzv[val], l, r);
      if(ans != -1){
        cout<<ans<<" "<<ans<<"\n";
        continue;
      }
      ans = query(pzl[val], l, r-1);
      if(ans!= -1){
        cout<<ans<<" "<<ans + 1<<"\n";
        continue;
      }
      cout<<"-1"<<" "<<"-1"<<"\n";
    }

  }
  return 0;
}

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