結果
問題 | No.1216 灯籠流し/Lanterns |
ユーザー |
![]() |
提出日時 | 2020-08-30 15:00:33 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,309 ms / 4,500 ms |
コード長 | 9,879 bytes |
コンパイル時間 | 2,492 ms |
コンパイル使用メモリ | 166,800 KB |
実行使用メモリ | 285,188 KB |
最終ジャッジ日時 | 2024-11-15 08:28:04 |
合計ジャッジ時間 | 28,158 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 48 |
ソースコード
#include <algorithm>#include <bitset>#include <cassert>#include <chrono>#include <climits>#include <cmath>#include <complex>#include <cstring>#include <deque>#include <functional>#include <iostream>#include <iomanip>#include <list>#include <map>#include <numeric>#include <queue>#include <random>#include <set>#include <stack>#include <unordered_map>#include <unordered_set>#include <vector>#include <cstdint>using namespace std;typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pii;#define MP make_pair#define PB push_back#define inf 1000000007#define rep(i,n) for(int i = 0; i < (int)(n); ++i)#define all(x) (x).begin(),(x).end()template<typename A, size_t N, typename T>void Fill(A (&array)[N], const T &val){std::fill( (T*)array, (T*)(array+N), val );}template<class T> inline bool chmax(T &a, T b){if(a<b){a = b;return true;}return false;}template<class T> inline bool chmin(T &a, T b){if(a>b){a = b;return true;}return false;}template<typename T> class segtree {private:int n,sz;vector<T> node;public:void init(const vector<T>& v){sz = (int)v.size();n = 1;while(n < sz){n *= 2;}node.assign(2*n,0);for(int i = 0; i < sz; i++){node[i+n] = v[i];}for(int i=n-1; i>=1; i--){node[i] =node[2*i] + node[2*i+1];}}void update(int k,T a){node[k+=n] += a;while(k>>=1){node[k] = node[2*k]+node[2*k+1];}}T query(int a,int b){T res1 = 0;T res2 = 0;a += n, b += n;while(a != b){if(a & 1) res1 = res1+node[a++];if(b & 1) res2 = node[--b]+ res2;a >>= 1, b>>= 1;}return res1+res2;}void print(){for(int i = 0; i < sz; i++){cout << query(i,i+1) << " ";}cout << endl;}};//座標の型, 値の型template<typename CandidateType, typename ValueType> class RangeTree{public:static_assert(std::is_integral<CandidateType>::value, "Integral required.");private:using CT = CandidateType;using VT = ValueType;using pcc = pair<CT, CT>;using pci = pair<CT, int>;int n, sz;vector<segtree<VT> > seg;// y座標, x座標vector<vector<pcc> > yx;// y座標, x座標vector<pcc> sorted;void update_(int id, const CT x, const CT y, const VT val) {id += n-1;const int yid = lower_bound(all(yx[id]), pcc(y, x)) - yx[id].begin();seg[id].update(yid, val);while(id > 0){id = (id - 1) / 2;const int yid = lower_bound(all(yx[id]), pcc(y, x)) - yx[id].begin();seg[id].update(yid, val);}}VT query(const int lxid, const int rxid, const CT ly, const CT ry, const int k, const int l, const int r) {if(r <= lxid || rxid <= l) return 0;if(lxid <= l && r <= rxid){const int lyid = lower_bound(all(yx[k]), pcc(ly, numeric_limits<CT>::min())) - yx[k].begin();const int ryid = upper_bound(all(yx[k]), pcc(ry, numeric_limits<CT>::min())) - yx[k].begin();return (lyid >= ryid) ? 0 : seg[k].query(lyid, ryid);}else{return query(lxid, rxid, ly, ry, 2*k+1, l, (l+r)/2) + query(lxid, rxid, ly, ry, 2*k+2, (l+r)/2, r);}}public:// 座標, 点の値RangeTree(const vector<pcc>& cand, const vector<VT>& val) : n(1), sz((int)cand.size()), sorted(sz){while(n < sz) n *= 2;for(int i = 0; i < sz; ++i){sorted[i] = {cand[i].first, i};}sort(all(sorted), [&](const pcc& a, const pcc& b){return (a.first == b.first) ? (cand[a.second].second < cand[b.second].second) : (a.first < b.first);});yx.resize(2*n-1), seg.resize(2*n-1);for(int i = 0; i < sz; ++i){yx[i+n-1] = {{sorted[i].second, sorted[i].first}};vector<VT> arg = {val[sorted[i].second]};seg[i+n-1].init(arg);sorted[i].second = cand[sorted[i].second].second;}for(int i = n-2; i >= 0; --i){yx[i].resize((int)yx[2*i+1].size() + (int)yx[2*i+2].size());if(yx[i].empty()) continue;merge(all(yx[2*i+1]), all(yx[2*i+2]), yx[i].begin(), [&](const pcc& a, const pcc& b){return (cand[a.first].second == cand[b.first].second)? (a.second < b.second) : (cand[a.first].second < cand[b.first].second);});vector<VT> arg((int)yx[i].size());for(int j = 0; j < (int)yx[i].size(); ++j){arg[j] = val[yx[i][j].first];}seg[i].init(arg);}for(int i = 0; i < 2*n-1; ++i){for(pcc& e : yx[i]){e.first = cand[e.first].second;}}}// 点 (x,y) の更新を行うvoid update(const CT x, const CT y, const VT val){const int id = lower_bound(all(sorted), pcc(x, y)) - sorted.begin();return update_(id, x, y, val);}// [lx,rx) × [ly,ry) の長方形領域のクエリに答えるVT query(const CT lx, const CT ly, const CT rx, const CT ry){const int lxid = lower_bound(all(sorted), pcc(lx, numeric_limits<CT>::min())) - sorted.begin();const int rxid = upper_bound(all(sorted), pcc(rx, numeric_limits<CT>::min())) - sorted.begin();return (lxid >= rxid) ? 0 : query(lxid, rxid, ly, ry, 0, 0, n);}};vector<vector<pair<int,ll> > > g;ll parent[17][50000];ll dep[50000];void init(int id,int pre){for(auto x:g[id]){if(x.first == pre)continue;dep[x.first] = dep[id] + x.second;parent[0][x.first] = id;init(x.first,id);}}vector<pair<ll,int>>add[50000];vector<pair<ll,int>>del[50000];vector<pair<ll,int>>question[50000];vector<pair<ll,ll> > cand[50000];set<pair<ll,ll> > q[50000];int leaf[50000];void cand_init(int id,int pre){int mx_size = -1;for(auto x:g[id]){if(x.first == pre)continue;cand_init(x.first,id);if(mx_size < (int)cand[leaf[x.first]].size()){mx_size = cand[leaf[x.first]].size();leaf[id] = leaf[x.first];}}if(mx_size==-1){leaf[id] = id;}else{for(auto x:g[id]){if(x.first==pre)continue;if(leaf[id]!=leaf[x.first]){for(auto &x:cand[leaf[x.first]]){cand[leaf[id]].push_back(x);}}}}for(auto x:add[id]){cand[leaf[id]].push_back(x);}for(auto x:question[id]){cand[leaf[id]].push_back(x);}}vector<RangeTree<ll,int>> rt;vector<pair<int,int> > ans;void ans_dfs(int id,int pre){for(auto x:g[id]){if(x.first == pre)continue;ans_dfs(x.first,id);}for(auto x:g[id]){if(x.first == pre)continue;if(leaf[x.first]!=leaf[id]){for(auto y:q[leaf[x.first]]){q[leaf[id]].insert(y);rt[leaf[id]].update(y.first,y.second,1);}}}// cerr << "answer" << endl;// cerr << id << endl;// for(auto x:q[leaf[id]]){// cerr << x.first << " " << x.second << endl;// }for(auto x:add[id]){rt[leaf[id]].update(x.first,x.second,1);q[leaf[id]].insert(x);}for(auto x:question[id]){ans.push_back({x.second,rt[leaf[id]].query(0,0,x.first+1,x.second+1)});}for(auto x:del[id]){rt[leaf[id]].update(x.first,x.second,-1);q[leaf[id]].erase(x);}}int main(){cin.tie(0);ios::sync_with_stdio(false);int n,Q;cin >> n >> Q;g.resize(n);rep(i,n-1){int a,b;ll c;cin >> a >> b >> c;a--;b--;g[a].push_back({b,c});g[b].push_back({a,c});}init(0,-1);vector<int> tlist;rep(tt,Q){int type,V;ll T,L;cin >> type >> V >> T >> L;V--;if(type==0){add[V].push_back({T+dep[V],tt});ll TT = T+dep[V];while(V!=0){bool ff = 0;for(int i=16;i>=0;i--){int P = parent[i][V];if(dep[V]-dep[P] <= L){ff = 1;L -= dep[V]-dep[P];V = P;break;}}if(!ff){break;}}del[V].push_back({TT,tt});}else{question[V].push_back({T+dep[V],tt});}}rep(i,50000){leaf[i] = -1;}cand_init(0,-1);rep(i,50000){vector<int> pp;rep(zz,cand[i].size()){pp.push_back(0);}rt.push_back(RangeTree<ll,int>(cand[i],pp));}// rep(i,n){// cout <<"test:" << i << " " << leaf[i] << endl;// cerr << "cand\n";// for(auto x:cand[i]){// cout << x.first << " " << x.second << endl;// }// cerr << "add\n";// for(auto x:add[i]){// cout << x.first << " " << x.second << endl;// }// cerr << "question\n";// for(auto x:question[i]){// cout << x.first << " " << x.second << endl;// }// cerr << "del\n";// for(auto x:del[i]){// cout << x.first << " " << x.second << endl;// }// }ans_dfs(0,-1);sort(all(ans));for(auto x:ans){cout << x.second << "\n";}return 0;}