結果

問題 No.1216 灯籠流し/Lanterns
ユーザー 👑 hos.lyric
提出日時 2020-08-30 16:00:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,705 ms / 4,500 ms
コード長 6,581 bytes
コンパイル時間 1,721 ms
コンパイル使用メモリ 137,248 KB
実行使用メモリ 146,792 KB
最終ジャッジ日時 2024-11-15 10:37:53
合計ジャッジ時間 36,701 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
int N, Q;
vector<int> A, B;
vector<Int> C;
vector<int> TYP, V;
vector<Int> T, L;
vector<vector<int>> G;
vector<int> par, sz, dep;
vector<Int> dist;
int O;
vector<int> ord, head;
void dfs0(int u, int p, int ip) {
par[u] = p;
sz[u] = 1;
dep[u] = (p == -1) ? 0 : (dep[p] + 1);
dist[u] = (p == -1) ? 0 : (dist[p] + C[ip]);
for (const int i : G[u]) {
const int v = A[i] ^ B[i] ^ u;
if (v != p) {
dfs0(v, u, i);
sz[u] += sz[v];
}
}
}
void dfs1(int u, int p, int h) {
ord[u] = O++;
head[u] = h;
int vm = -1;
for (const int i : G[u]) {
const int v = A[i] ^ B[i] ^ u;
if (v != p) {
if (vm == -1 || sz[vm] < sz[v]) {
vm = v;
}
}
}
if (vm != -1) {
dfs1(vm, u, h);
for (const int i : G[u]) {
const int v = A[i] ^ B[i] ^ u;
if (v != p && v != vm) {
dfs1(v, u, v);
}
}
}
}
int BIT_N;
struct BIT {
map<int, int> as;
void add(int pos, int val) {
for (int x = pos; x < BIT_N; x |= x + 1) {
as[x] += val;
}
}
int sum(int pos) {
int ret = 0;
for (int x = pos - 1; x >= 0; x = (x & (x + 1)) - 1) {
auto it = as.find(x);
if (it != as.end()) {
ret += it->second;
}
}
return ret;
}
};
constexpr int E = 16;
int main() {
for (; ~scanf("%d%d", &N, &Q); ) {
A.resize(N - 1);
B.resize(N - 1);
C.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d%lld", &A[i], &B[i], &C[i]);
--A[i];
--B[i];
}
TYP.resize(Q);
V.resize(Q);
T.resize(Q);
L.resize(Q);
for (int q = 0; q < Q; ++q) {
scanf("%d%d%lld%lld", &TYP[q], &V[q], &T[q], &L[q]);
--V[q];
}
G.assign(N, {});
for (int i = 0; i < N - 1; ++i) {
G[A[i]].push_back(i);
G[B[i]].push_back(i);
}
par.resize(N);
sz.resize(N);
dep.resize(N);
dist.resize(N);
constexpr int rt = 0;
dfs0(rt, -1, -1);
O = 0;
ord.resize(N);
head.resize(N);
dfs1(rt, -1, rt);
// cerr<<"dist = ";pv(dist.begin(),dist.end());
// cerr<<"ord = ";pv(ord.begin(),ord.end());
// cerr<<"head = ";pv(head.begin(),head.end());
vector<int> lens(N, 0);
for (int u = 0; u < N; ++u) {
++lens[head[u]];
}
BIT_N = Q;
vector<vector<BIT>> bits(N);
for (int h = 0; h < N; ++h) {
bits[h].assign(lens[h], {});
}
auto bAdd = [&](int h, int pos, int key, int val) {
// cerr<<"bAdd "<<h<<" "<<pos<<" "<<key<<" "<<val<<endl;
for (int x = pos; x < lens[h]; x |= x + 1) {
bits[h][x].add(key, val);
}
};
auto bSum = [&](int h, int pos, int key) {
int ret = 0;
for (int x = pos - 1; x >= 0; x = (x & (x + 1)) - 1) {
ret += bits[h][x].sum(key);
}
return ret;
};
// the path from u to root
auto hldAdd = [&](int u, int key, int val) {
// cerr<<"hldAdd "<<u<<" "<<key<<" "<<val<<endl;
for (; u != -1; ) {
const int h = head[u];
// add to [0, ord[u] - ord[h]]
// cerr<<" "<<h<<" "<<(lens[h] - (ord[u] - ord[h]) - 1)<<endl;
bAdd(h, lens[h] - (ord[u] - ord[h]) - 1, key, val);
u = par[h];
}
};
auto hldSum = [&](int u, int key) {
// cerr<<"hldSum "<<u<<" "<<key<<endl;
const int h = head[u];
// sum at (ord[u] - ord[h])
// cerr<<" "<<h<<" "<<(lens[h] - (ord[u] - ord[h]))<<endl;
const int ret = bSum(h, lens[h] - (ord[u] - ord[h]), key);
return ret;
};
vector<vector<int>> pp(E, vector<int>(N));
vector<vector<Int>> dd(E, vector<Int>(N));
pp[0] = par;
for (int u = 0; u < N; ++u) {
dd[0][u] = (par[u] == -1) ? 0 : (dist[u] - dist[par[u]]);
}
for (int e = 0; e < E - 1; ++e) {
for (int u = 0; u < N; ++u) {
if (pp[e][u] == -1) {
pp[e + 1][u] = -1;
dd[e + 1][u] = dd[e][u];
} else {
pp[e + 1][u] = pp[e][pp[e][u]];
dd[e + 1][u] = dd[e][u] + dd[e][pp[e][u]];
}
}
}
/*
vector<int>brt(Q,-58);
if(N<=2000&&Q<=2000){
vector<vector<Int>>wss(N);
for(int q=0;q<Q;++q){
if(TYP[q]==0){
for(int u=V[q];u!=-1&&dist[V[q]]-dist[u]<=L[q];u=par[u]){
// cerr<<"brt add "<<u<<" "<<T[q]+dist[V[q]]<<endl;
wss[u].push_back(T[q]+dist[V[q]]);
}
}else{
sort(wss[V[q]].begin(),wss[V[q]].end());
brt[q]=upper_bound(wss[V[q]].begin(),wss[V[q]].end(),T[q]+dist[V[q]])-wss[V[q]].begin();
// printf("%d\n",brt[q]);
}
}
// continue;
}
// exit(1);
//*/
vector<int> ans(Q, -58);
vector<pair<pair<Int, int>, int>> qrys(Q);
for (int q = 0; q < Q; ++q) {
qrys[q] = make_pair(make_pair(T[q] + dist[V[q]], TYP[q]), q);
}
sort(qrys.begin(), qrys.end());
for (const auto &qry : qrys) {
const int q = qry.second;
switch (TYP[q]) {
case 0: {
Int l = L[q];
int u = V[q];
for (int e = E; e--; ) {
if (pp[e][u] != -1 && l - dd[e][u] >= 0) {
l -= dd[e][u];
u = pp[e][u];
}
}
// cerr<<"q = "<<q<<": u = "<<u<<endl;
assert(dist[V[q]]-dist[u]<=L[q]);
if(par[u]!=-1)assert(dist[V[q]]-dist[par[u]]>L[q]);
hldAdd(V[q], q, +1);
hldAdd(par[u], q, -1);
} break;
case 1: {
// cerr<<"q = "<<q<<endl;
ans[q] = hldSum(V[q], q);
} break;
default: assert(false);
}
}
for (int q = 0; q < Q; ++q) {
if (TYP[q] == 1) {
printf("%d\n", ans[q]);
}
}
/*
if(N<=2000&&Q<=2000){
for(int q=0;q<Q;++q)if(brt[q]!=ans[q]){
cerr<<"q = "<<q<<": "<<brt[q]<<" "<<ans[q]<<endl;
assert(false);
}
}
//*/
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0