#725044 (C++14) No.1790 Subtree Deletion

• 問題: No.1790 Subtree Deletion
• ユーザー: tails
• 提出日時: 2021-12-19 07:13:08
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 60 ms / 3,000 ms
• コード長: 9,286 bytes
• コンパイル時間: 2,481 ms
• コンパイル使用メモリ: 188,008 KB
• 実行使用メモリ: 17,920 KB
• 最終ジャッジ日時: 2024-09-15 14:25:35
• 合計ジャッジ時間: 3,992 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 12

ソースコード

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
void*wmem;
char memarr[96000000];
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  walloc1d(arr, x2-x1, mem);
  (*arr) -= x1;
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(long long &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(unsigned long long &x){
  int k;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(unsigned long long x){
  int s=0;
  char f[21];
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
template<class T> struct segtree_ph{
  int N;
  int logN;
  T*val;
  void malloc(int maxN, int once = 0);
  void walloc(int maxN, int once = 0, void **mem = &wmem);
  void free(void);
  T& operator[](int i);
  void setN(int n, int zerofill = 1, int dobuild = 1);
  void build(void);
  inline void build(int a);
  inline void change(int a, T v);
  inline void changed(int a);
  inline T get(int a, int b);
  inline T getleft(int b);
}
;
struct graph{
  int N;
  int*es;
  int**edge;
  void setEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
    int i;
    N = N__;
    walloc1d(&es, N, mem);
    walloc1d(&edge, N, mem);
    for(i=(0);i<(N);i++){
      es[i] = 0;
    }
    for(i=(0);i<(M);i++){
      es[A[i]]++;
      es[B[i]]++;
    }
    for(i=(0);i<(N);i++){
      walloc1d(&edge[i], es[i], mem);
    }
    for(i=(0);i<(N);i++){
      es[i] = 0;
    }
    for(i=(0);i<(M);i++){
      edge[A[i]][es[A[i]]++] = B[i];
      edge[B[i]][es[B[i]]++] = A[i];
    }
  }
}
;
template<class T> struct wgraph{
  int N;
  int*es;
  int**edge;
  T**cost;
  graph g;
  void setEdge(int N__, int M, int A[], int B[], T C[], void **mem = &wmem){
    int i;
    N = N__;
    walloc1d(&es, N, mem);
    for(i=(0);i<(N);i++){
      es[i] = 0;
    }
    for(i=(0);i<(M);i++){
      es[A[i]]++;
      es[B[i]]++;
    }
    walloc1d(&edge, N, mem);
    for(i=(0);i<(N);i++){
      walloc1d(&edge[i], es[i], mem);
    }
    walloc1d(&cost, N, mem);
    for(i=(0);i<(N);i++){
      walloc1d(&cost[i], es[i], mem);
    }
    for(i=(0);i<(N);i++){
      es[i] = 0;
    }
    for(i=(0);i<(M);i++){
      edge[A[i]][es[A[i]]] = B[i];
      edge[B[i]][es[B[i]]] = A[i];
      cost[A[i]][es[A[i]]++] = C[i];
      cost[B[i]][es[B[i]]++] = C[i];
    }
    g.N = N;
    g.es = es;
    g.edge = edge;
  }
}
;
wgraph<unsigned long long> g;
unsigned long long na[100000+1];
struct{
  int l;
  int r;
}
lr[100000+1];
int f(int i,int p,int x){
  int j;
  lr[i].l=x++;
  int Nzj9Y0kE = g.es[i];
  for(j=(0);j<(Nzj9Y0kE);j++){
    int k=g.edge[i][j];
    if(k!=p){
      x=f(k,i,x);
    }
    else{
      na[lr[i].l]=g.cost[i][j];
    }
  }
  lr[i].r=x;
  return x;
}
int l[100000];
int r[100000];
unsigned long long a[100000];
struct segt{
  unsigned long long a;
  int d;
  int e;
}
;
inline segt segtree_ph_func(segt a,segt b){
  segt r;
  int d=a.d-b.e;
  r.d=(d>=0?d:0)+b.d;
  r.e=(d>=0?0:-d)+a.e;
  r.a=(d>=0?a.a:0)^(d<=0?b.a:0);
  return r;
}
int main(){
  int OA9NF42T, i;
  wmem = memarr;
  long long n;
  rd(n);
  {
    int QAAnbtfa;
    for(QAAnbtfa=(0);QAAnbtfa<(n-1);QAAnbtfa++){
      rd(l[QAAnbtfa]);
      rd(r[QAAnbtfa]);
      rd(a[QAAnbtfa]);
    }
  }
  g.setEdge(n+1,n-1,l,r,a);
  f(1,0,1);
  segtree_ph<segt> t;
  t.walloc(n+2,1);
  t[0]=segt{0,0,0};
  t[n+1]=segt{0,0,0};
  for(i=(1);i<(n+1);i++){
    t[i]=segt{na[i],0,0};
  }
  t.build();
  long long q;
  rd(q);
  for(OA9NF42T=(0);OA9NF42T<(q);OA9NF42T++){
    long long w;
    rd(w);
    long long x;
    rd(x);
    if(w==1){
      {
        int i=lr[x].l-1;
        t[i].d+=1;
        t.changed(i);
      }
      {
        int i=lr[x].r;
        t[i].e+=1;
        t.changed(i);
      }
    }
    if(w==2){
      unsigned long long z=0;
      segt s1=t.getleft(lr[x].l);
      if(s1.d<=t[lr[x].l].e){
        segt s2=t.getleft(lr[x].r);
        z=s1.a^s2.a^na[lr[x].l];
      }
      wt_L(z);
      wt_L('\n');
    }
  }
  return 0;
}
template<class T> void segtree_ph<T>::malloc(int maxN, int once /*= 0*/){
  int i;
  for(i=1;i<maxN;i*=2){
    ;
  }
  val = new T[2*i];
  if(once){
    setN(maxN);
  }
}
template<class T> void segtree_ph<T>::walloc(int maxN, int once /*= 0*/, void **mem /*= &wmem*/){
  int i;
  for(i=1;i<maxN;i*=2){
    ;
  }
  walloc1d(&val, 2*i, mem);
  if(once){
    setN(maxN);
  }
}
template<class T> void segtree_ph<T>::free(void){
  delete [] val;
}
template<class T> T& segtree_ph<T>::operator[](int i){
  return val[N+i];
}
template<class T> void segtree_ph<T>::setN(int n, int zerofill /*= 1*/, int dobuild /*= 1*/){
  int i;
  for(i=1,logN=0;i<n;i*=2,logN++){
    ;
  }
  N = i;
  if(dobuild){
    build();
  }
}
template<class T> void segtree_ph<T>::build(void){
  for(int i=N-1;i;i--){
    val[i] = segtree_ph_func(val[2*i], val[2*i+1]);
  }
}
template<class T> inline void segtree_ph<T>::build(int a){
  while(a > 1){
    a /= 2;
    val[a] = segtree_ph_func(val[2*a], val[2*a+1]);
  }
}
template<class T> inline void segtree_ph<T>::change(int a, T v){
  val[a+N] = v;
  build(a+N);
}
template<class T> inline void segtree_ph<T>::changed(int a){
  build(a+N);
}
template<class T> inline T segtree_ph<T>::get(int a, int b){
  T res;
  T tmp;
  int fga = 0;
  int fgb = 0;
  a += N;
  b += N;
  while(a < b){
    if(a%2){
      if(fga){
        res = segtree_ph_func(res, val[a]);
      }
      else{
        res = val[a];
        fga = 1;
      }
      a++;
    }
    if(b%2){
      b--;
      if(fgb){
        tmp = segtree_ph_func(val[b], tmp);
      }
      else{
        tmp = val[b];
        fgb = 1;
      }
    }
    a /= 2;
    b /= 2;
  }
  if(fga==1 && fgb==0){
    return res;
  }
  if(fga==0 && fgb==1){
    return tmp;
  }
  if(fga==1 && fgb==1){
    return segtree_ph_func(res, tmp);
  }
  return res;
}
template<class T> inline T segtree_ph<T>::getleft(int b){
  T tmp;
  int fgb = 0;
  b += N;
  while(0 < b){
    if(b%2){
      b--;
      if(fgb){
        tmp = segtree_ph_func(val[b], tmp);
      }
      else{
        tmp = val[b];
        fgb = 1;
      }
    }
    b /= 2;
  }
  return tmp;
}

// (modified code generated by)
// cLay version 20211024-1

// --- original code ---
// //yukicoder@clay
// wgraph<ull> g;
// ull na[1d5+1];
// struct{int l,r;}lr[1d5+1];
// 
// int f(int i,int p,int x){
// 	lr[i].l=x++;
// 	REP(j,g.es[i]){
// 		int k=g.edge[i][j];
// 		if(k!=p){
// 			x=f(k,i,x);
// 		}else{
// 			na[lr[i].l]=g.cost[i][j];
// 		}
// 	}
// 	lr[i].r=x;
// 	return x;
// }
// 
// int l[1d5],r[];
// ull a[];
// 
// struct segt {
// 	ull a;
// 	int d,e;
// };
// 
// inline
// segt segtree_ph_func(segt a,segt b){
// 	segt r;
// 	int d=a.d-b.e;
// 	r.d=(d>=0?d:0)+b.d;
// 	r.e=(d>=0?0:-d)+a.e;
// 	r.a=(d>=0?a.a:0)^(d<=0?b.a:0);
// 	return r;
// }
// 
// {
// 	ll@n;
// 	rd((l,r,a)(n-1));
// 	g.setEdge(n+1,n-1,l,r,a);
// 	f(1,0,1);
// 	segtree_ph<segt> t;
// 	t.walloc(n+2,1);
// 	t[0]=segt{0,0,0};
// 	t[n+1]=segt{0,0,0};
// 	rep(i,1,n+1){
// 		t[i]=segt{na[i],0,0};
// 	}
// 	t.build();
// 	ll@q;
// 	rep(q){
// 		ll@w,@x;
// 		if(w==1){
// 			{
// 				int i=lr[x].l-1;
// 				t[i].d+=1;
// 				t.changed(i);
// 			}
// 			{
// 				int i=lr[x].r;
// 				t[i].e+=1;
// 				t.changed(i);
// 			}
// 		}
// 		if(w==2){
// 			ull z=0;
// 			segt s1=t.getleft(lr[x].l);
// 			if(s1.d<=t[lr[x].l].e){
// 				segt s2=t.getleft(lr[x].r);
// 				z=s1.a^s2.a^na[lr[x].l];
// 			}
// 			wt(z);
// 		}
// 	}
// }