結果

問題 No.1216 灯籠流し/Lanterns
ユーザー beet
提出日時 2020-08-30 16:03:53
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 9,783 bytes
コンパイル時間 5,020 ms
コンパイル使用メモリ 280,872 KB
最終ジャッジ日時 2025-01-13 23:31:17
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 45 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0