結果
| 問題 | No.1216 灯籠流し/Lanterns |
| ユーザー |
 kaage
|
| 提出日時 | 2020-08-01 13:44:31 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,121 bytes |
| コンパイル時間 | 1,950 ms |
| コンパイル使用メモリ | 153,156 KB |
| 実行使用メモリ | 26,184 KB |
| 最終ジャッジ日時 | 2024-07-18 11:59:12 |
| 合計ジャッジ時間 | 4,956 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | WA | - |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
ソースコード
#line 2 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp"
#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i,n) for(int i=0;i<(lint)(n);i++)
#define REP(i,n) for(int i=1;i<=(lint)(n);i++)
#define all(V) V.begin(),V.end()
typedef long long lint;
typedef unsigned long long ulint;
typedef std::pair<int, int> P;
typedef std::pair<lint, lint> LP;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;
constexpr double eps = DBL_EPSILON;
constexpr double PI=3.141592653589793238462643383279;
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
if (lhs < rhs) {
lhs = rhs;
return 1;
}
return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
if (lhs > rhs) {
lhs = rhs;
return 1;
}
return 0;
}
inline lint gcd(lint a, lint b) {
while (b) {
lint c = a;
a = b; b = c % b;
}
return a;
}
inline lint lcm(lint a, lint b) {
return a / gcd(a, b) * b;
}
bool isprime(lint n) {
if (n == 1)return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0)return false;
}
return true;
}
template<typename T>
T mypow(T a, lint b) {
if (!b)return T(1);
if (b & 1)return mypow(a, b - 1) * a;
T memo = mypow(a, b >> 1);
return memo * memo;
}
lint modpow(lint a, lint b, lint m) {
if (!b)return 1;
if (b & 1)return modpow(a, b - 1, m) * a % m;
lint memo = modpow(a, b >> 1, m);
return memo * memo % m;
}
template<typename T>
void printArray(std::vector<T>& vec) {
rep(i, vec.size() - 1)std::cout << vec[i] << " ";
std::cout << vec.back() << std::endl;
}
template<typename T>
void printArray(T l, T r) {
T rprev = r;
rprev--;
for (T i = l; i != rprev; i++) {
std::cout << *i << " ";
}
std::cout << *rprev << std::endl;
}
#line 3 "/Users/kaage/Desktop/ProgrammingWorkspace/library/data-structure/BIT.hpp"
class BIT {
int n;
std::vector<lint> bit;
public:
BIT(unsigned int n) :n(n) {
bit.resize(n + 1, 0);
}
void add(int a, lint x) {
while (a <= n) {
bit[a] += x;
a += a & -a;
}
}
lint query(int a) {
lint cnt = 0;
while (a > 0) {
cnt += bit[a];
a -= a & -a;
}
return cnt;
}
void clear() {
bit.assign(n + 1, 0);
}
unsigned int lower_bound(int x){
int p=0,k=1;
while(k*2<=n)k*=2;
while(k>0){
if(p+k<=n&&bit[p+k]<x){
x-=bit[p+k];
p+=k;
}
k/=2;
}
return p+1;
}
unsigned int upper_bound(int x){
int p=0,k=1;
while(k*2<=n)k*=2;
while(k>0){
if(p+k<=n&&bit[p+k]<=x){
x-=bit[p+k];
p+=k;
}
k/=2;
}
return p+1;
}
};
#line 3 "main.cpp"
int N,Q;
int type[500010],v[500010];
lint t[500010],l[500010];
int ans[500010];
std::vector<std::pair<int,lint>> vec[200010],children[200010],comped[200010];
std::vector<std::pair<std::pair<lint,int>,std::pair<int,lint>>> queries[200010];
LP newpar[200010],repr[200010];
bool used[200010];
std::set<int> verset;
void dfs(int node){
used[node]=true;
for(const auto& i:vec[node]){
if(!used[i.first]){
children[node].emplace_back(i);
dfs(i.first);
}
}
}
void compress(int node,int par,lint dist){
used[node]=true;
bool use=verset.find(node)!=verset.end();
newpar[node]={par,dist};
if(use){
comped[par].emplace_back(node,dist);
repr[node]={node,0};
}
else repr[node]=newpar[node];
for(const auto& i:children[node]){
if(!used[i.first]){
if(use)compress(i.first,node,i.second);
else compress(i.first,par,dist+i.second);
}
}
}
int main(){
freopen("tests/02_random11.txt","r",stdin);
scanf("%d %d",&N,&Q);
rep(i,N-1){
int a,b;
lint c;
scanf("%d %d %lld",&a,&b,&c);
vec[a].emplace_back(b,c);
vec[b].emplace_back(a,c);
}
rep(i,Q)scanf("%d %d %lld %lld",type+i,v+i,t+i,l+i);
dfs(1);
std::vector<lint> cords;
std::queue<std::pair<std::pair<int,lint>,int>> que;
BIT bit(2*Q);
int B=sqrt(Q);
for(int i=0;i<Q;i+=B){
std::cerr<<i<<"\n";
verset.clear();
verset.insert(1);
for(int j=i;j<std::min(Q,i+B);j++){
if(type[j]==1)verset.insert(v[j]);
}
memset(used,false,sizeof(used));
REP(j,N){
comped[j].clear();
queries[j].clear();
}
compress(1,0,0);
rep(j,i){
if(type[j]==0&&l[j]-repr[v[j]].second>=0){
queries[repr[v[j]].first].push_back({{t[j]+repr[v[j]].second,0},{0,l[j]-repr[v[j]].second}});
}
}
for(int j=i;j<std::min(Q,i+B);j++){
if(type[j]==1){
que.push({{v[j],0},0});
while(!que.empty()){
auto p=que.front();
que.pop();
queries[p.first.first].push_back({{t[j]-p.first.second,1},{j,p.first.second}});
for(const auto& k:comped[p.first.first]){
if(k.first!=p.second&&p.first.second+k.second<=t[j]){
que.push({{k.first,p.first.second+k.second},p.first.first});
}
}
}
}
}
REP(j,N){
if(verset.find(j)!=verset.end()){
std::sort(all(queries[j]));
cords.clear();
for(const auto& k:queries[j])cords.emplace_back(k.second.second);
std::sort(all(cords));
cords.erase(std::unique(all(cords)),cords.end());
for(auto& k:queries[j])k.second.second=std::lower_bound(all(cords),k.second.second)-cords.begin()+1;
for(const auto& k:queries[j]){
if(k.first.second==0)bit.add(k.second.second,1);
else {
ans[k.second.first]+=bit.query(cords.size()+1);
if(k.second.second!=1)ans[k.second.first]-=bit.query(k.second.second-1);
}
}
for(const auto& k:queries[j]){
if(k.first.second==0)bit.add(k.second.second,-1);
}
queries[j].clear();
}
}
for(int j=std::min(Q,i+B)-1;j>=i;j--){
if(type[j]==0){
int node=v[j];
lint time=t[j];
while(time-t[j]<=l[j]){
for(const auto& k:queries[node]){
if(time<=k.first.first)ans[k.first.second]++;
}
if(node==1)break;
time+=newpar[node].second;
node=newpar[node].first;
}
}
else queries[v[j]].push_back({{t[j],j},{0,0}});
}
}
rep(i,Q){
if(type[i]==1)printf("%d\n",ans[i]);
}
}