QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#185164#6737. NeighbourhoodbulijiojiodibuliduoRE 0ms0kbC++4.9kb2023-09-21 18:22:382023-09-21 18:22:39

Judging History

你现在查看的是最新测评结果

  • [2023-09-21 18:22:39]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-09-21 18:22:38]
  • 提交

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

output:


result: