oj.uz

Submission #175999

# Submission time Handle Problem Language Result Execution time Memory
175999 2020-01-07T14:16:34 Z itgl Birthday gift (IZhO18_treearray) C++14
0 / 100
 12 ms 6648 KB 
#include<bits/stdc++.h>

using namespace std;
int n, m, q;
int a1[200005];
vector<int> adj[200005];
int lvl[200005];
int a[200005][30];
inline void dfs(int u, int x, int l){
  a[u][0]=x;
  lvl[u]=l;
  for(int i=0;i<adj[u].size();i++){
    int v=adj[u][i];
    if(v!=x){
      dfs(v,u,l+1);
    }
  }
}
inline void solve(){
  for(int j=1;j<=18;j++){
    for(int i=1;i<=n;i++){
      a[i][j]=a[a[i][j-1]][j-1];
    }
  }
}
inline int query(int x, int y){
  int l1=lvl[x];
  int l2=lvl[y];
  if(l1<l2){
    swap(l1,l2);
    swap(x,y);
  }
  while(l1!=l2){
    for(int j=18;j>=0;j--){
      if(l1-(1<<j)>=l2){
        l1=l1-(1<<j);
        x=a[x][j];
      }
    }
  }
  for(int j=18;j>=0;j--){
    int u=a[x][j];
    int v=a[y][j];
    if(u!=v){
      x=u;
      y=v;
    }
  }
  return a[x][0];
}

inline int lca(int x, int y){
  int l1=lvl[x];
  int l2=lvl[y];
  if(l1<l2){
    swap(l1,l2);
    swap(x,y);
  }
  while(l1!=l2){
    for(int j=18;j>=0;j--){
      if(l1-(1<<j)>=l2){
        l1=l1-(1<<j);
        x=a[x][j];
      }
    }
  }
  if(x==y) return x;
  for(int j=18;j>=0;j--){
    int u=a[x][j];
    int v=a[y][j];
    if(u!=v){
      x=u;
      y=v;
    }
  }
  return a[x][0];
}
int tree[400005];
int x,y;
bool ch=0;
inline void build(int id, int l, int r, int L, int v){
  if(l==r){
    tree[id]=a1[L+l-1];
    if(tree[id]==v){
      x=l+L-1;
      y=r+L-1;
    }
    return;
  }
  build(id*2,l,(l+r)/2,L,v);
  build(id*2+1,(l+r)/2+1,r,L,v);
  tree[id]=lca(tree[id*2],tree[id*2+1]);
  if(tree[id]==v){
    x=l+L-1;
    y=r+L-1;
  }
}

inline void sol(int l, int r, int v){
  x=-1,y=-1;
  //cout << a1[r] << endl;
  memset(tree,0,sizeof(tree));
  build(1,1,(r-l+1),l,v);
  cout << x << ' ' << y << endl;
  return;
}

int main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n >> m >> q;
  for(int i=1;i<n;i++){
    int u, v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1,0,1);
  solve();
  //cout << "YES";
  for(int i=1;i<=m;i++) cin >> a1[i];

  while(q--){
    int k;
    cin >>k;
    if(k==1){
      int pos,val;
      cin >>pos>>val;
      a1[pos]=val;
    }else{
        int l,r,v;
        cin >> l >> r >> v;
        sol(l,r,v);
      }
    }



  return 0;
}

Compilation message

treearray.cpp: In function 'void dfs(int, int, int)':
treearray.cpp:12:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<adj[u].size();i++){
               ~^~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6648 KB n=5
2 Incorrect 12 ms 6648 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6648 KB n=5
2 Incorrect 12 ms 6648 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6648 KB n=5
2 Incorrect 12 ms 6648 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6648 KB n=5
2 Incorrect 12 ms 6648 KB Jury has the answer but participant has not
3 Halted 0 ms 0 KB -