Submission #695050

#	Time	Username	Problem	Language	Result	Execution time	Memory
695050		Abrar_Al_Samit	Birthday gift (IZhO18_treearray)	C++17	0 / 100	1 ms	468 KiB

treearray

#include<bits/stdc++.h>
using namespace std;

const int nax = 2004;

vector<int>g[nax];

int n, m, q;
int a[nax];
int sp[nax][18];
int tt(0);
int st[nax], en[nax], dep[nax];
int tree[nax * 4];

bool anc(int x, int y) {
  return st[x]<=st[y] && en[x]>=en[y];
}
int getlca(int x, int y) {
  if(x==0) return y;
  if(y==0) return x;

  for(int j=17; j>=0; --j) {
    if(!anc(sp[x][j], y)) {
      x = sp[x][j];
    }
  }
  if(!anc(x, y)) x = sp[x][0];
  return x;
}
void DFS(int v, int par = 1) {
  dep[v] = 1+dep[par];
  st[v] = tt++;

  sp[v][0] = par;
  for(int j=1; j<18; ++j) {
    sp[v][j] = sp[sp[v][j-1]][j-1];
  }

  for(int u : g[v]) if(u!=par) {
    DFS(u, v);
  }
  en[v] = tt++;
}

void build(int l, int r, int v) {
  if(l==r) {
    tree[v] = a[l];
    return;
  }
  int mid = (l+r)/2;
  build(l, mid, v*2);
  build(mid+1, r, v*2+1);

  tree[v] = getlca(tree[v*2], tree[v*2+1]);
}
void upd(int l, int r, int i, int val, int v) {
  if(l==r) {
    tree[v] = val;
    return;
  }
  int mid = (l+r)/2;
  if(i<=mid) upd(l, mid, i, val, v*2);
  else upd(mid+1, r, i, val, v*2+1);
  tree[v] = getlca(tree[v*2], tree[v*2+1]);
}

int query(int l, int r, int L, int R, int v) {
  if(l>=L && r<=R) return tree[v];
  if(l>R || r<L) return 0;

  int mid = (l+r)/2;
  return getlca(query(l, mid, L, R, v*2), query(mid+1, r, L, R, v*2+1));
}
void PlayGround() {
  cin>>n>>m>>q;

  for(int i=1; i<n; ++i) {
    int u, v;
    cin>>u>>v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for(int i=1; i<=m; ++i) {
    cin>>a[i];
  }

  dep[1] = -1;
  DFS(1);
  build(1, m, 1);

  while(q--) {
    int t;
    cin>>t;
    if(t==1) {
      int pos, v;
      cin>>pos>>v;
      upd(1, m, pos, v, 1);
      a[pos] = v;
    } else {
      int l, r, v;
      cin>>l>>r>>v;

      int p0=l, p1=l;

      int x(-1), y(-1);

      int cur = a[l];
      while(p0<=r) {
        while(p1<r && dep[cur]>dep[v]) {
          ++p1;
          cur = getlca(cur, a[p1]);
        }
        if(cur==v) {
          x = p0, y = p1;
          break;
        }

        ++p0;
        cur = query(1, m, p0, p1, 1);

        //cerr<<p0<<' '<<p1<<' '<<cur<<endl;
      }

      cout<<x<<' '<<y<<'\n';
    } 
  }


  // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

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