QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#412666 | #6737. Neighbourhood | Thankto_zy6 | RE | 0ms | 0kb | C++14 | 5.6kb | 2024-05-16 17:20:28 | 2024-05-16 17:20:29 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ii;
int he[200005],to[400005],ne[400005],id[400005],cnt;
ii w[200005];
void link(int u,int v,int w){
cnt++;
to[cnt]=v;
ne[cnt]=he[u];
id[cnt]=w;
he[u]=cnt;
}
int B;
bool bdr[200005];
int bel[200005],bee[200005],stk[200005],_top[200005],top;
int cl[200005],clutop;
int up[200005],down[200005];
struct nodd{
int id;
ii v;
};
bool operator<(nodd x,nodd y){
return x.v<y.v;
}
vector<nodd>dis[200005][2];int clu;
int ef[200005],fa[200005],wait[200005],low[200005];
ii dud[200005];
int tag[200005];
void puttag(int x,int pr,int k,int tg){
tag[x]=tg;
for(int i=he[x];i;i=ne[i]){
if(to[i]!=pr&&bel[to[i]]==k){
puttag(to[i],x,k,tg);
}
}
}
void getdud(int i){
int x=down[i];dud[i]=0;
if(!x)return;
while(x!=up[i]){
dud[i]+=w[ef[x]];
x=fa[x];
}
}
int get(int x,int i){
return (x==up[i])?0:1;
}
struct node{
int v,i;
};
vector<node>eg[200005];
void add_clu(int u,int v){
clu++;
bdr[u]=1;up[clu]=u;
if(!v)v=cl[clutop];
eg[u].push_back({v,clu});
down[clu]=v;bdr[v]=1;
eg[v].push_back({u,clu});
clutop=0;
}
void dfs(int x){
wait[x]=1;int tot=0;_top[x]=top;
for(int i=he[x];i;i=ne[i]){
if(to[i]==fa[x])continue;
ef[to[i]]=id[i];fa[to[i]]=x;stk[++top]=to[i];
dfs(to[i]);
wait[x]+=wait[to[i]];
if(low[to[i]])low[x]=low[to[i]],tot++;
}
if(tot>1||wait[x]>=B||!fa[x]){
wait[x]=0;
low[x]=x;
for(int i=he[x],cur=0,j=_top[x]+1,wt=0;;i=ne[i]){
if(to[i]==fa[x]&&fa[x])continue;
int v=to[i];
if(wt+wait[v]>B||!v||(cur&&low[v])){
for(;(j<_top[v]||!v)&&j<=top;j++){
cl[++clutop]=stk[j];
if(!bel[stk[j]])bel[stk[j]]=clu+1;
if(stk[j]!=x){
if(!bee[ef[stk[j]]])bee[ef[stk[j]]]=clu+1;
}
}
add_clu(x,cur);
wt=cur=0;
}
wt+=wait[v];
if(low[v])cur=low[v];
if(!i)break;
}
}
}
void sear(int x,int pr,int k,int bz,ii ds){
if(!bdr[x])dis[k][bz].push_back({x,ds});
for(int i=he[x];i;i=ne[i]){
if(to[i]!=pr&&(bel[to[i]]==k||to[i]==up[k]||to[i]==down[k])){
sear(to[i],x,k,bz,ds+w[id[i]]);
}
}
}
void pre(int x,int i){
if(!x)return;
int bz=get(x,i);
vector<nodd>().swap(dis[i][bz]);
sear(x,0,i,bz,0);
sort(dis[i][bz].begin(),dis[i][bz].end());
}
int flg[200005];
void sear2(int x,int pr,int k,int tg,int sw){
flg[x]=sw;
for(int i=he[x];i;i=ne[i]){
if(to[i]!=pr&&(bel[to[i]]==k||to[i]==up[k]||to[i]==down[k])){
if(id[i]==tg){
sear2(to[i],x,k,tg,1);
}
else{
sear2(to[i],x,k,tg,sw);
}
}
}
}
nodd ttmp1[200005],ttmp2[200005];int top1,top2;
void pre2(int x,int i,int tg,ii delta){
if(!x)return;top1=top2=0;
int bz=get(x,i);
sear2(x,0,i,tg,0);
for(nodd v:dis[i][bz]){
if(flg[v.id])ttmp2[++top2]={v.id,v.v+delta};
else ttmp1[++top1]=v;
}
vector<nodd>().swap(dis[i][bz]);
int j=1,k=1;
while(j<=top1&&k<=top2){
if(ttmp1[j].v<ttmp2[k].v){
dis[i][bz].push_back(ttmp1[j]);
j++;
}
else{
dis[i][bz].push_back(ttmp2[k]);
k++;
}
}
while(j<=top1){
dis[i][bz].push_back(ttmp1[j]);
j++;
}
while(k<=top2){
dis[i][bz].push_back(ttmp2[k]);
k++;
}
}
int qry_clu(int x,int i,ii k){
if(!x)return 0;
int bz=get(x,i);
if(dis[i][bz].empty())return 0;
if((dis[i][bz].back()).v<=k){
return dis[i][bz].size();
}
int l=1,r=dis[i][bz].size(),mid;
while(l<r){
mid=(l+r)>>1;
if(dis[i][bz][mid-1].v<=k)l=mid+1;
else r=mid;
}
// cerr<<"!"<<x<<" "<<i<<" "<<k<<" "<<l-1<<endl;
return l-1;
}
int res;
ii d1,d2;
void qry1(int x,int y,int pr,ii ds,ii k){
if(x==up[y])d1=ds;
if(x==down[y])d2=ds;
// if(bdr[x])return;
if(ds<=k&&!bdr[x])res++;
for(int i=he[x];i;i=ne[i]){
if(to[i]!=pr&&(bel[to[i]]==y||to[i]==up[y]||to[i]==down[y])){
qry1(to[i],y,x,ds+w[id[i]],k);
}
}
}
int qry2(int x,int pr,ii k){
int ret=1;
if(k<0)return 0;
for(node v:eg[x]){
if(v.v!=pr){
ret+=qry_clu(x,v.i,k);
if(k>=dud[v.i]&&v.v){
ret+=qry2(v.v,x,k-dud[v.i]);
}
}
}
return ret;
}
int main(){
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
int n,q;
scanf("%d%d",&n,&q);B=500;
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d%lld",&u,&v,&w[i]);
link(u,v,i);
link(v,u,i);
}
dfs(1);//cerr<<"**"<<clu<<endl;
for(int i=1;i<=clu;i++){
pre(up[i],i);
if(down[i])pre(down[i],i);
int x=down[i];dud[i]=0;
if(!x)continue;
int o=0;
while(x!=up[i]){
dud[i]+=w[ef[x]];
for(int j=he[x];j;j=ne[j]){
if(bel[to[j]]==i&&to[j]!=o&&to[j]!=fa[x]){
puttag(to[j],x,i,x);
}
if(!bdr[x])tag[x]=x;
}
o=x;
x=fa[x];
}
for(int j=he[up[x]];j;j=ne[j]){
if(bel[to[j]]==i&&to[j]!=o){
puttag(to[j],up[x],i,up[x]);
}
}
}
while(q--){
int opt;
scanf("%d",&opt);
if(opt==1){
int i;ii c,d;
scanf("%d%lld",&i,&c);d=c-w[i];
w[i]=c;
int k=bee[i];
pre2(up[k],k,i,d);
if(down[k])pre2(down[k],k,i,d);
getdud(k);
}
else{
int x;ii d;
scanf("%d%lld",&x,&d);
res=0;
if(!bdr[x]){
if(tag[x]!=up[bel[x]]&&tag[x]!=down[bel[x]]){
qry1(x,bel[x],0,0,d);
res+=qry2(up[bel[x]],down[bel[x]],d-d1);
res+=qry2(down[bel[x]],up[bel[x]],d-d2);
}
else{
if(tag[x]==up[bel[x]]){
qry1(x,bel[x],0,0,d);
res+=qry2(up[bel[x]],0,d-d1);
res-=qry_clu(up[bel[x]],bel[x],d-d1);
}
if(tag[x]==down[bel[x]]){
qry1(x,bel[x],0,0,d);
res+=qry2(down[bel[x]],0,d-d2);
res-=qry_clu(down[bel[x]],bel[x],d-d2);
}
}
}
else{
res=qry2(x,-1,d);
}
printf("%d\n",res);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
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