QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#185164 | #6737. Neighbourhood | bulijiojiodibuliduo | RE | 0ms | 0kb | C++ | 4.9kb | 2023-09-21 18:22:38 | 2023-09-21 18:22:39 |
answer
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=201000;
vector<array<int,2>> e[N];
int wt[N];
int q[N],f[N],vis[N],sz[N],ms[N];
int find(int u) {
int t=1;q[0]=u;f[u]=-1;
rep(i,0,t) {
u=q[i];
rep(j,0,e[u].size()) {
int v=e[u][j][0];
if (!vis[v]&&v!=f[u]) f[q[t++]=v]=u;
}
ms[q[i]]=0;
sz[q[i]]=1;
}
for (int i=t-1;i>=0;i--) {
ms[q[i]]=max(ms[q[i]],t-sz[q[i]]);
if (ms[q[i]]*2<=t) return q[i];
sz[f[q[i]]]+=sz[q[i]];
ms[f[q[i]]]=max(ms[f[q[i]]],sz[q[i]]);
}
return 0;
}
int M=15;
struct dst {
vector<ll> val;
vector<ll> ordval;
int n,len;
VI be,cnt;
vector<ll> mx,mn,tag;
void init(vector<ll> dp) {
val=dp;
ordval=dp;
n=SZ(dp);
len=sqrt(n*0.5)+0.1;
len=min(len,n);
be.resize(n);
mx=vector<ll>(n/len+1,-(1ll<<60));
mn=vector<ll>(n/len+1,(1ll<<60));
tag=vector<ll>(n/len+1,0);
cnt=vector<int>(n/len+1,0);
rep(i,0,n) {
be[i]=i/len;
mx[be[i]]=max(mx[be[i]],val[i]);
mn[be[i]]=min(mn[be[i]],val[i]);
}
}
#define le(i) (i * len)
#define re(i) (i * len + len - 1)
void add(int l,int r,ll c) {
int lim = min(r, re(be[l]));
cnt[be[l]]=0;
for (int i = l; i <= lim; ++ i) {
val[i] += c;
mx[be[l]] = max(mx[be[l]], val[i]);
mn[be[l]] = min(mn[be[l]], val[i]);
}
if (be[l] == be[r]) return;
cnt[be[r]]=0;
for (int i = le(be[r]); i <= r; ++ i) {
val[i] += c;
mx[be[r]] = max(mx[be[r]], val[i]);
mn[be[r]] = min(mn[be[r]], val[i]);
}
for (int i = be[l] + 1; i <= be[r] - 1; ++ i) {
tag[i] += c;
}
}
int query(int l, int r, ll c) {
++c;
int ans = 0, lim = min(r, re(be[l]));
for (int i = l; i <= lim; ++ i) {
if (mn[be[l]] + tag[be[l]] >= c) {
break ;
}
if (mx[be[l]] + tag[be[l]] < c) {
ans += (lim - l + 1);
break ;
}
(val[i] + tag[be[l]] < c) ? ++ ans : ans;
}
if (be[l] == be[r]) return ans;
for (int i = le(be[r]); i <= r; ++ i) {
if (mn[be[r]] + tag[be[r]] >= c) {
break ;
}
if (mx[be[r]] + tag[be[r]] < c) {
ans += (r - le(be[r]) + 1);
break ;
}
(val[i] + tag[be[r]] < c) ? ++ ans : ans;
}
for (int i = be[l] + 1; i <= be[r] - 1; ++ i) {
if (mn[i] + tag[i] >= c) {
continue ;
}
if (mx[i] + tag[i] < c) {
ans += len;
continue ;
}
cnt[i]++;
if (cnt[i]==M) {
for (int j = le(i); j <= re(i); ++ j) {
ordval[j]=val[j];
}
sort(ordval.begin()+le(i),ordval.begin()+re(i)+1);
mx[i]=ordval[re(i)];
mn[i]=ordval[le(i)];
}
if (cnt[i]<M) {
for (int j = le(i); j <= re(i); ++ j) {
(val[j] + tag[i] < c) ? ++ ans : ans;
}
} else {
ans+=lower_bound(ordval.begin()+le(i),ordval.begin()+re(i)+1,
c-tag[i])-(ordval.begin()+le(i));
}
}
return ans;
}
ll queryp(int x) {
return val[x]+tag[be[x]];
}
}ds[N];
int n,Q;
vector<array<int,3>> ps[N];
vector<array<int,4>> cs[N];
void solve(int x) {
x=find(x);
vis[x]=1;
int tot=0;
static int l[N],r[N],br[N];
VI pv;
vector<ll> dp;
function<void(int,int,int,ll)> dfs=[&](int u,int f,int b,ll dep) {
l[u]=tot++;
dp.pb(dep);
pv.pb(u);
br[u]=b;
for (auto [v,id]:e[u]) if (v!=f&&!vis[v]) {
dfs(v,u,b==-1?v:b,dep+wt[id]);
ps[id].pb({x,l[v],r[v]});
}
r[u]=tot-1;
};
dfs(x,-1,-1,0);
ds[x].init(dp);
for (auto u:pv) {
if (br[u]==-1) {
cs[u].pb({x,0,tot-1,l[u]});
} else {
if (l[br[u]]-1>=0) {
cs[u].pb({x,0,l[br[u]]-1,l[u]});
}
if (r[br[u]]+1<tot) {
cs[u].pb({x,r[br[u]]+1,tot-1,l[u]});
}
}
}
for (auto [v,id]:e[x]) if (!vis[v]) {
solve(v);
}
}
int main() {
scanf("%d%d",&n,&Q);
rep(i,1,n) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[u].pb({v,i});
e[v].pb({u,i});
wt[i]=w;
}
solve(1);
rep(i,0,Q) {
int op;
scanf("%d",&op);
if (op==1) {
int id,c;
scanf("%d%d",&id,&c);
c-=wt[id]; wt[id]+=c;
for (auto [x,l,r]:ps[id]) {
ds[x].add(l,r,c);
}
} else {
int x; ll d;
scanf("%d%lld",&x,&d);
int ans=0;
for (auto [u,l,r,pos]:cs[x]) {
ll v=ds[u].queryp(pos);
ans+=ds[u].query(l,r,d-v);
}
printf("%d\n",ans);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 7 1 2 3 2 3 1 2 2 1 2 1 3 2 3 4 1 1 1 2 2 1 2 1 0 2 3 1