結果

問題 No.1216 灯籠流し/Lanterns
ユーザー beetbeet
提出日時 2020-08-30 16:03:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 9,783 bytes
コンパイル時間 4,716 ms
コンパイル使用メモリ 293,400 KB
実行使用メモリ 54,464 KB
最終ジャッジ日時 2024-11-15 10:46:08
合計ジャッジ時間 88,224 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 52 ms
16,128 KB
testcase_05 TLE -
testcase_06 AC 269 ms
8,832 KB
testcase_07 AC 4,405 ms
40,948 KB
testcase_08 AC 3,730 ms
31,264 KB
testcase_09 AC 1,604 ms
22,944 KB
testcase_10 AC 1,709 ms
20,892 KB
testcase_11 AC 643 ms
19,252 KB
testcase_12 AC 47 ms
13,312 KB
testcase_13 AC 707 ms
25,344 KB
testcase_14 AC 165 ms
15,872 KB
testcase_15 AC 330 ms
19,140 KB
testcase_16 AC 259 ms
23,808 KB
testcase_17 AC 1,568 ms
27,524 KB
testcase_18 AC 395 ms
18,892 KB
testcase_19 AC 2,232 ms
46,036 KB
testcase_20 AC 955 ms
30,160 KB
testcase_21 AC 460 ms
21,984 KB
testcase_22 AC 1,762 ms
33,840 KB
testcase_23 AC 78 ms
19,960 KB
testcase_24 AC 245 ms
8,576 KB
testcase_25 AC 109 ms
6,912 KB
testcase_26 AC 1,835 ms
19,904 KB
testcase_27 AC 418 ms
17,280 KB
testcase_28 AC 195 ms
18,432 KB
testcase_29 AC 686 ms
25,600 KB
testcase_30 AC 1,341 ms
26,868 KB
testcase_31 AC 2,912 ms
30,676 KB
testcase_32 AC 1,083 ms
27,776 KB
testcase_33 AC 185 ms
14,720 KB
testcase_34 TLE -
testcase_35 AC 2,477 ms
54,464 KB
testcase_36 AC 1,559 ms
43,668 KB
testcase_37 AC 2,090 ms
30,936 KB
testcase_38 AC 3,862 ms
46,064 KB
testcase_39 AC 4,005 ms
47,128 KB
testcase_40 AC 2,598 ms
50,036 KB
testcase_41 AC 2,521 ms
50,068 KB
testcase_42 AC 2,496 ms
49,808 KB
testcase_43 AC 2,527 ms
50,076 KB
testcase_44 AC 2,515 ms
49,920 KB
testcase_45 AC 2,858 ms
53,676 KB
testcase_46 AC 2,856 ms
53,856 KB
testcase_47 AC 2,866 ms
53,584 KB
testcase_48 AC 2,825 ms
53,632 KB
testcase_49 AC 3,106 ms
53,660 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}

struct Sack{
  using F = function<void(int)>;
  int n;
  vector<int> sz,hvy,big;
  vector<vector<int> > G,Q;
  F expand,shrink,query,reset;

  Sack(int n,F expand,F shrink,F query,F reset):
    sz(n,1),hvy(n,-1),big(n,0),G(n),Q(n),
    expand(expand),shrink(shrink),
    query(query),reset(reset){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void add_query(int v,int k){
    Q[v].emplace_back(k);
    sz[v]++;
  }

  void add(int v,int p,int x){
    if(x==1) expand(v);
    else shrink(v);
    for(int u:G[v])
      if(u!=p&&!big[u]) add(u,v,x);
  }

  void dfs(int v=0,int p=-1,bool k=0){
    for(int u:G[v])
      if(u!=p&&u!=hvy[v]) dfs(u,v,0);
    if(~hvy[v]){
      dfs(hvy[v],v,1);
      big[hvy[v]]=1;
    }
    add(v,p,1);
    for(int k:Q[v]) query(k);
    if(~hvy[v]) big[hvy[v]]=0;
    if(!k) add(v,p,0),reset(v);
  }

  void build(int v=0,int p=-1){
    for(int u:G[v]){
      if(u==p) continue;
      build(u,v);
      if(hvy[v]<0||sz[hvy[v]]<sz[u]) hvy[v]=u;
      sz[v]+=sz[u];
    }
    if(p==-1) dfs(v,p);
  }
};

class EulerTourForVertex{
private:
  vector<int> ls,rs;
  int pos;

  void dfs(int v,int p){
    ls[v]=pos++;
    for(int u:G[v])
      if(u!=p) dfs(u,v);
    rs[v]=pos;
  }

public:
  vector< vector<int> > G;

  EulerTourForVertex(){}
  EulerTourForVertex(int n):ls(n),rs(n),G(n){}

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void build(int r=0){
    pos=0;
    dfs(r,-1);
  }

  int idx(int v){return ls[v];}

  template<typename F>
  void exec(int v,F f){
    f(ls[v],rs[v]);
  }
};


struct LowestCommonAncestor{
  int n,h;
  vector< vector<int> > G,par;
  vector<int> dep;
  LowestCommonAncestor(){}
  LowestCommonAncestor(int n):n(n),G(n),dep(n){
    h=1;
    while((1<<h)<=n) h++;
    par.assign(h,vector<int>(n,-1));
  }

  void add_edge(int u,int v){
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }

  void dfs(int v,int p,int d){
    par[0][v]=p;
    dep[v]=d;
    for(int u:G[v])
      if(u!=p) dfs(u,v,d+1);
  }

  void build(int r=0){
    dfs(r,-1,0);
    for(int k=0;k+1<h;k++)
      for(int v=0;v<n;v++)
        if(~par[k][v])
          par[k+1][v]=par[k][par[k][v]];
  }

  int lca(int u,int v){
    if(dep[u]>dep[v]) swap(u,v);
    for(int k=0;k<h;k++)
      if((dep[v]-dep[u])>>k&1)
        v=par[k][v];

    if(u==v) return u;

    for(int k=h-1;k>=0;k--)
      if(par[k][u]!=par[k][v])
        u=par[k][u],v=par[k][v];

    return par[0][u];
  }

  int distance(int u,int v){
    return dep[u]+dep[v]-dep[lca(u,v)]*2;
  }
};


struct AuxiliaryTree : EulerTourForVertex{
  using super = EulerTourForVertex;
  LowestCommonAncestor lca;

  vector<vector<int>> T;
  AuxiliaryTree(){}
  AuxiliaryTree(int n):super(n),lca(n),T(n){}

  void build(int r=0){
    super::build(r);
    lca.G=super::G;
    lca.build(r);
  }

  void add_aux_edge(int u,int v){
    T[u].emplace_back(v);
    T[v].emplace_back(u);
  }

  using super::idx;
  void query(vector<int> &vs){
    assert(!vs.empty());
    sort(vs.begin(),vs.end(),
         [&](int a,int b){return idx(a)<idx(b);});
    vs.erase(unique(vs.begin(),vs.end()),vs.end());

    int k=vs.size();
    stack<int> st;
    st.emplace(vs[0]);
    for(int i=0;i+1<k;i++){
      int w=lca.lca(vs[i],vs[i+1]);
      if(w!=vs[i]){
        int l=st.top();st.pop();
        while(!st.empty()&&lca.dep[w]<lca.dep[st.top()]){
          add_aux_edge(st.top(),l);
          l=st.top();st.pop();
        }
        if(st.empty()||st.top()!=w){
          st.emplace(w);
          vs.emplace_back(w);
        }
        add_aux_edge(w,l);
      }
      st.emplace(vs[i+1]);
    }

    while(st.size()>1){
      int c=st.top();st.pop();
      add_aux_edge(st.top(),c);
    }
  }

  void clear(const vector<int> &ws){
    for(int w:ws) T[w].clear();
  }
};


template<typename T>
struct RangeCount{
  struct BIT{
    vector<T> dat;
    BIT(){}
    BIT(int n){dat.assign(++n,0);}
    T sum(int k){
      T res=0;
      for(;k;k-=k&-k) res+=dat[k];
      return res;
    }
    void add(int k,T v){
      for(++k;k<(int)dat.size();k+=k&-k) dat[k]+=v;
    }
  };
  int n;
  using ll = long long;
  vector< vector<ll> > val;
  vector<BIT> dat;
  RangeCount(){}
  RangeCount(int n_){
    n=1;
    while(n<n_) n<<=1;
    val.assign(n<<1,vector<ll>());
    dat.reserve(n<<1);
  }
  void preupdate(int a,ll x){
    a+=n;
    while(a){
      val[a].emplace_back(x);
      a>>=1;
    }
  }
  void build(){
    for(int i=0;i<n*2;i++){
      auto &v=val[i];
      sort(v.begin(),v.end());
      v.erase(unique(v.begin(),v.end()),v.end());
      dat.emplace_back(v.size());
    }
  }
  void update(int a,ll x,T z){
    a+=n;
    while(a){
      auto &v=val[a];
      int k=lower_bound(v.begin(),v.end(),x)-v.begin();
      dat[a].add(k,z);
      a>>=1;
    }
  }
  T calc(int k,ll x,ll y){
    auto &v=val[k];
    int p=lower_bound(v.begin(),v.end(),x)-v.begin();
    int q=lower_bound(v.begin(),v.end(),y)-v.begin();
    return dat[k].sum(q)-dat[k].sum(p);
  }
  // [a, b) * [x, y)
  T query(int a,int b,ll x,ll y){
    T res=0;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1){
      if(l&1) res+=calc(l++,x,y);
      if(r&1) res+=calc(--r,x,y);
    }
    return res;
  }
};


template<typename TV, const int N> void read_tuple_impl(TV&) {}
template<typename TV, const int N, typename Head, typename... Tail>
void read_tuple_impl(TV& ts) {
  get<N>(ts).emplace_back(*(istream_iterator<Head>(cin)));
  read_tuple_impl<TV, N+1, Tail...>(ts);
}
template<typename... Ts> decltype(auto) read_tuple(size_t n) {
  tuple<vector<Ts>...> ts;
  for(size_t i=0;i<n;i++) read_tuple_impl<decltype(ts), 0, Ts...>(ts);
  return ts;
}

template<typename F>
struct FixPoint : F{
  FixPoint(F&& f):F(forward<F>(f)){}
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const{
    return F::operator()(*this,forward<Args>(args)...);
  }
};
template<typename F>
inline decltype(auto) MFP(F&& f){
  return FixPoint<F>{forward<F>(f)};
}


template<typename V>
V compress(V vs){
  sort(vs.begin(),vs.end());
  vs.erase(unique(vs.begin(),vs.end()),vs.end());
  return vs;
}
template<typename T>
map<T, int> dict(const vector<T> &vs){
  map<T, int> res;
  for(int i=0;i<(int)vs.size();i++)
    res[vs[i]]=i;
  return res;
}
map<char, int> dict(const string &s){
  return dict(vector<char>(s.begin(),s.end()));
}


using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;

// AtCoder
const i64 CYCLES_PER_SEC = 2800000000;

struct Timer {
	i64 start;
	Timer(){reset();}
	void reset(){start=getCycle();}
	inline double get(){return (double)(getCycle()-start)/CYCLES_PER_SEC;}
	inline i64 getCycle(){
		u32 low,high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((i64)low)|((i64)high<<32);
	}
};

Timer timer;

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  using ll = long long;

  int n,q;
  cin>>n>>q;
  using P = pair<int, ll>;
  vector<vector<P>> G(n);
  AuxiliaryTree H(n);
  for(int i=1;i<n;i++){
    int a,b;
    ll c;
    cin>>a>>b>>c;
    a--;b--;
    G[a].emplace_back(b,c);
    G[b].emplace_back(a,c);
    H.add_edge(a,b);
  }
  H.build(0);

  vector<ll> dep(n);
  MFP([&](auto dfs,int v,int p,ll d)->void{
    dep[v]=d;
    for(auto [u,c]:G[v])
      if(u!=p) dfs(u,v,d+c);
  })(0,-1,0);

  auto [type,vs,ts,ls]=read_tuple<int, int, ll, ll>(q);
  for(int &v:vs) v--;
  vector<int> ans(q);

  queue<P> que;
  que.emplace(0,q);

  while(!que.empty()){
    if(timer.get()>4.0) break;

    auto [L,R]=que.front();que.pop();
    if(L+1==R) continue;
    int M=(L+R)>>1;

    vector<int> ss;
    for(int i=L;i<M;i++)
      if(type[i]==0) ss.emplace_back(vs[i]);

    for(int i=M;i<R;i++)
      if(type[i]==1) ss.emplace_back(vs[i]);

    if(ss.empty()){
      que.emplace(L,M);
      que.emplace(M,R);
      continue;
    }

    ss.emplace_back(0);

    H.query(ss);
    ss=compress(ss);
    auto dc=dict(ss);

    int m=ss.size();
    vector<vector<int>> B(m);
    for(int i=L;i<M;i++)
      if(type[i]==0) B[dc[vs[i]]].emplace_back(i);

    vector<ll> pos;
    for(int i=L;i<M;i++)
      if(type[i]==0) pos.emplace_back(ts[i]+dep[vs[i]]);

    for(int i=M;i<R;i++)
      if(type[i]==1) pos.emplace_back(ts[i]+dep[vs[i]]);

    pos=compress(pos);
    auto rev=dict(pos);

    RangeCount<int> seg(pos.size());
    for(int i=L;i<M;i++)
      if(type[i]==0)
        seg.preupdate(rev[ts[i]+dep[vs[i]]],dep[vs[i]]-ls[i]);
    seg.build();

    auto expand=[&](int v){
      for(int i:B[v])
        seg.update(rev[ts[i]+dep[vs[i]]],dep[vs[i]]-ls[i],+1);
    };
    auto shrink=[&](int v){
      for(int i:B[v])
        seg.update(rev[ts[i]+dep[vs[i]]],dep[vs[i]]-ls[i],-1);
    };
    auto query=[&](int i){
      if(type[i]==1)
        ans[i]+=seg.query(0,rev[ts[i]+dep[vs[i]]]+1,-1e18,dep[vs[i]]+1);
    };
    auto reset=[&](int){};

    Sack S(m,expand,shrink,query,reset);

    for(int v:ss)
      for(int u:H.T[v])
        if(v<u) S.add_edge(dc[u],dc[v]);

    for(int i=L;i<M;i++)
      if(type[i]==0) S.add_query(dc[vs[i]],i);

    for(int i=M;i<R;i++)
      if(type[i]==1) S.add_query(dc[vs[i]],i);

    S.build(dc[0]);

    H.clear(ss);

    que.emplace(L,M);
    que.emplace(M,R);
  }

  for(int i=0;i<q;i++)
    if(type[i]==1) cout<<ans[i]<<newl;
  return 0;
}
0