結果
問題 | No.1216 灯籠流し/Lanterns |
ユーザー | autumn-eel |
提出日時 | 2020-08-02 16:13:33 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,333 ms / 4,500 ms |
コード長 | 3,410 bytes |
コンパイル時間 | 2,366 ms |
コンパイル使用メモリ | 190,196 KB |
実行使用メモリ | 229,836 KB |
最終ジャッジ日時 | 2023-08-09 10:52:34 |
合計ジャッジ時間 | 23,555 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
21,124 KB |
testcase_01 | AC | 9 ms
21,128 KB |
testcase_02 | AC | 8 ms
21,128 KB |
testcase_03 | AC | 8 ms
21,136 KB |
testcase_04 | AC | 37 ms
23,384 KB |
testcase_05 | AC | 292 ms
219,440 KB |
testcase_06 | AC | 37 ms
43,928 KB |
testcase_07 | AC | 273 ms
220,528 KB |
testcase_08 | AC | 237 ms
206,720 KB |
testcase_09 | AC | 128 ms
113,708 KB |
testcase_10 | AC | 135 ms
123,440 KB |
testcase_11 | AC | 75 ms
63,216 KB |
testcase_12 | AC | 30 ms
23,692 KB |
testcase_13 | AC | 95 ms
65,252 KB |
testcase_14 | AC | 60 ms
40,220 KB |
testcase_15 | AC | 107 ms
58,208 KB |
testcase_16 | AC | 97 ms
47,816 KB |
testcase_17 | AC | 462 ms
195,340 KB |
testcase_18 | AC | 122 ms
65,800 KB |
testcase_19 | AC | 509 ms
225,264 KB |
testcase_20 | AC | 255 ms
115,544 KB |
testcase_21 | AC | 132 ms
69,732 KB |
testcase_22 | AC | 389 ms
198,512 KB |
testcase_23 | AC | 47 ms
26,380 KB |
testcase_24 | AC | 34 ms
41,792 KB |
testcase_25 | AC | 22 ms
30,924 KB |
testcase_26 | AC | 136 ms
128,752 KB |
testcase_27 | AC | 62 ms
51,316 KB |
testcase_28 | AC | 54 ms
35,640 KB |
testcase_29 | AC | 93 ms
63,464 KB |
testcase_30 | AC | 121 ms
94,212 KB |
testcase_31 | AC | 189 ms
167,340 KB |
testcase_32 | AC | 119 ms
84,680 KB |
testcase_33 | AC | 46 ms
35,452 KB |
testcase_34 | AC | 289 ms
227,124 KB |
testcase_35 | AC | 1,115 ms
228,520 KB |
testcase_36 | AC | 1,080 ms
229,836 KB |
testcase_37 | AC | 117 ms
26,700 KB |
testcase_38 | AC | 519 ms
226,620 KB |
testcase_39 | AC | 1,333 ms
226,596 KB |
testcase_40 | AC | 1,059 ms
228,904 KB |
testcase_41 | AC | 1,056 ms
228,772 KB |
testcase_42 | AC | 1,039 ms
228,772 KB |
testcase_43 | AC | 1,079 ms
228,984 KB |
testcase_44 | AC | 1,099 ms
229,056 KB |
testcase_45 | AC | 490 ms
228,560 KB |
testcase_46 | AC | 486 ms
228,716 KB |
testcase_47 | AC | 485 ms
228,608 KB |
testcase_48 | AC | 484 ms
228,552 KB |
testcase_49 | AC | 481 ms
227,516 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n)for(int i=0;i<(n);i++) using namespace std; typedef long long ll; typedef pair<ll,ll>P; struct BIT2D{ vector<vector<int>>bit; BIT2D(){} BIT2D(int n,int m){ bit=vector<vector<int>>(n+10,vector<int>(m+10)); } void add(int a,int b,int val){ for(int x=a+1;x<bit.size();x+=x&-x){ for(int y=b+1;y<bit[x].size();y+=y&-y){ bit[x][y]+=val; } } } int sum(int a,int b){ int res=0; for(int x=a+1;x;x-=x&-x){ for(int y=b+1;y;y-=y&-y){ res+=bit[x][y]; } } return res; } }; vector<P>E[60000]; ll d[60000]; //深さ int vid[60000],rev[60000]; //Euler Tour上の頂点の順番 int cl[60000],cr[60000]; //部分木に対応する区間 int node_cnt; void dfs(int v,int p){ cl[v]=node_cnt; vid[v]=node_cnt++; rev[vid[v]]=v; for(auto u:E[v]){ if(u.second==p)continue; d[u.second]=d[v]+u.first; dfs(u.second,v); } cr[v]=node_cnt; } int ty[200000],v[200000]; ll t[200000],l[200000]; struct st{ ll v; //頂点のid P p; //(出発時間、持続時間) int id; //何番目に追加される? int X,Y; //bucketで使う情報 }; const int B=1000; vector<st>vs; //全灯籠の列 (Euler Tour順序でソート) int pos[200000]; struct Bucket{ BIT2D bit; vector<ll>xs,ys; vector<int>idx; void pre_add(st&s){ ll X=s.p.first+d[s.v],Y=d[s.v]-s.p.second; xs.push_back(X); ys.push_back(Y); idx.push_back(pos[s.id]); } void init(){ sort(xs.begin(),xs.end());xs.erase(unique(xs.begin(),xs.end()),xs.end()); sort(ys.begin(),ys.end());ys.erase(unique(ys.begin(),ys.end()),ys.end()); for(int i:idx){ vs[i].X=lower_bound(xs.begin(),xs.end(),vs[i].p.first+d[vs[i].v])-xs.begin(); vs[i].Y=lower_bound(ys.begin(),ys.end(),d[vs[i].v]-vs[i].p.second)-ys.begin(); } bit=BIT2D(xs.size(),ys.size()); } void add(int id){ bit.add(vs[id].X,vs[id].Y,1); } int query(ll x,ll y){ x=upper_bound(xs.begin(),xs.end(),x)-xs.begin(); y=upper_bound(ys.begin(),ys.end(),y)-ys.begin(); return bit.sum(x-1,y-1); } }bucket[100000]; int main(){ int n,q;cin>>n>>q; assert(1<=n&&n<=50000); assert(1<=q&&q<=100000); rep(i,n-1){ int a,b;ll c;scanf("%d%d%lld",&a,&b,&c);a--;b--; E[a].push_back(P(c,b)); E[b].push_back(P(c,a)); } dfs(0,-1); rep(i,q){ scanf("%d%d%lld%lld",&ty[i],&v[i],&t[i],&l[i]);v[i]--; if(ty[i]==0)vs.push_back({v[i],P(t[i],l[i]),i}); } sort(vs.begin(),vs.end(),[&](st a,st b){return vid[a.v]<vid[b.v];}); rep(i,vs.size()){ pos[vs[i].id]=i; } for(int i=0;i<vs.size();i+=B){ for(int j=i;j<i+B&&j<vs.size();j++){ bucket[i/B].pre_add(vs[j]); } bucket[i/B].init(); } rep(i,n){ int ok1=vs.size(),ng1=-1; while(ok1-ng1>1){ int t=(ok1+ng1)/2; if(vid[vs[t].v]>=cl[i])ok1=t; else ng1=t; } int ok2=vs.size(),ng2=-1; while(ok2-ng2>1){ int t=(ok2+ng2)/2; if(vid[vs[t].v]>=cr[i])ok2=t; else ng2=t; } cl[i]=ok1; cr[i]=ok2; } rep(i,q){ if(ty[i]==0){ bucket[pos[i]/B].add(pos[i]); } else{ int L=cl[v[i]],R=cr[v[i]]; int ans=0; ll X=d[v[i]]+t[i],Y=d[v[i]]; while(L<R&&L%B!=0){ if(vs[L].id<=i&&vs[L].p.first+d[vs[L].v]<=X &&d[vs[L].v]-vs[L].p.second<=Y)ans++; L++; } while(L<R&&R%B!=0){ R--; if(vs[R].id<=i&&vs[R].p.first+d[vs[R].v]<=X&& d[vs[R].v]-vs[R].p.second<=Y)ans++; } for(int i=L;i<R;i+=B){ ans+=bucket[i/B].query(X,Y); } printf("%d\n",ans); } } }