結果
問題 | No.1216 灯籠流し/Lanterns |
ユーザー |
|
提出日時 | 2020-08-01 19:19:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,003 bytes |
コンパイル時間 | 1,626 ms |
コンパイル使用メモリ | 173,972 KB |
実行使用メモリ | 21,632 KB |
最終ジャッジ日時 | 2024-07-18 11:59:33 |
合計ジャッジ時間 | 20,423 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 TLE * 1 -- * 14 |
ソースコード
#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; vector<P>E[60000]; ll d[60000]; int vid[60000],rev[60000]; int cl[60000],cr[60000]; multiset<P>se[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 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){ int ty,v;ll t,l;scanf("%d%d%lld%lld",&ty,&v,&t,&l);v--; if(ty==0){ se[vid[v]].insert(P(t,l)); } else{ assert(l==0); int cnt=0; for(int i=cl[v];i<cr[v];i++){ int u=rev[i]; ll D=d[u]-d[v]; for(auto&p:se[i]){ if(p.first>t-D)break; if(D<=p.second)cnt++; } } printf("%d\n",cnt); } } }