泉州企业建站模板,扁平化网站模板下载,wap网站制作需要多少钱,wordpress ping地址L-WeChat Walk 每个大点记录一下邻接点的最大步数
每次修改的时候#xff0c;枚举修改点的邻接的大点来更新
修改大点的时候直接判是不是比邻接点都大 代码抄的std好不容易才看懂~
Code1
#includebits/stdc.h
using namespace std;
template class Tint T…L-WeChat Walk 每个大点记录一下邻接点的最大步数
每次修改的时候枚举修改点的邻接的大点来更新
修改大点的时候直接判是不是比邻接点都大 代码抄的std好不容易才看懂~
Code1
#includebits/stdc.h
using namespace std;
template class Tint T rd()
{T res0;char chgetchar();while(!isdigit(ch)) chgetchar();while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res;
}
const int N200010;
vectorint d[N],g[N]; // d原图 g大点
int n,m,q,Bs;
int id[N],cnt;
int a[N];
int chmp[N],mx[N];
int h[550][20010];
int ne[N4],e[N4],idx;
int ans[N];
void add(int u)
{for(int v:g[u]){int sid[v];e[idx]u,ne[idx]h[s][a[u]],h[s][a[u]]idx;;}
}
int main()
{nrd(),mrd(),qrd();Bs2*sqrt(m)1;memset(h,-1,sizeof h);for(int i1;im;i){int urd(),vrd();d[u].push_back(v);d[v].push_back(u);}// 一个点周围的大点for(int i1;in;i) for(int v:d[i]) if(d[v].size()Bs) g[i].push_back(v);for(int i1;in;i) if(d[i].size()Bs) id[i]cnt;// 大点编号for(int i1;iq;i){int urd(),wrd(); a[u]w;if(chmp[u]) {add(u);for(int v:g[u]) mx[v]max(mx[v],a[u]);continue;}if(!id[u])// 由于a的增加使得周围某些点冠军状态被破坏 {while(1){int k0,num0;for(int v:d[u]){nummax(num,a[v]);if(chmp[v](k0||a[v]a[k])) kv;// 找到步数最小的冠军}if(!k)// 周围已经没有冠军 {if(numa[u]) chmp[u]i,add(u); // 看看自己是不是冠军break;}if(a[k]a[u]) break;// 如果步数最小的冠军大于a[u]那么已经不会打破周围点的冠军状态ans[k]i-chmp[k];chmp[k]0;// 更新周围点的冠军状态 累计答案}}else{int sid[u];for(int ta[u]-w1;ta[u];t) // a[u]1~a[u]w{for(int jh[s][t];j!-1;jne[j]){int ve[j];if(a[v]tchmp[v]) ans[v]i-chmp[v],chmp[v]0;}}if(mx[u]a[u]) chmp[u]i,add(u);}for(int v:g[u]) mx[v]max(mx[v],a[u]);}for(int i1;in;i) if(chmp[i]) ans[i]q-chmp[i];for(int i1;in;i) printf(%d\n,ans[i]);return 0;
}Code2
KeHe大佬题解配合jiangly giegie的代码 考虑按步数 www 从大到小枚举
设 fuf_ufu表示 uuu 最近一次更新步数的时刻 lastu\text{last}_ulastu表示 uuu 上一次更新步数的时刻初值均为最终时刻qqq
若 uuu 为小点直接暴力算周围的点。
若 uuu 为大点考虑直接维护这个结果记为 mnv\text{mn}_vmnv)即每个点步数更新时枚举其周围所有大点 vvv 来更新 mnv\text{mn}_vmnv由于每个点周围的大点的个数不超过mBs\frac{m}{\text{Bs}}Bsm复杂度可行
#includebits/stdc.h
using namespace std;
template class Tint T rd()
{T res0;char chgetchar();while(!isdigit(ch)) chgetchar();while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res;
}
const int N200010;
int n,m,q,Bs;
vectorint e[N],big[N];
int walk[N],mx[N];
int ans[N];
vectorpairint,int event[10005];
int main()
{nrd(),mrd(),qrd();Bs2*sqrt(m)1;for(int i1;im;i){int urd(),vrd();e[u].push_back(v);e[v].push_back(u);}for(int i1;in;i) for(int v:e[i]) if(e[v].size()Bs) big[i].push_back(v);for(int i1;iq;i){int urd(),wrd();walk[u]w;event[walk[u]].push_back({u,i});}vectorint f(n1,q),last(n1,q),mn(n,q);for(int w10000;w1;w--){for(auto [u,t]:event[w]) {for(auto v:big[u])mn[v]min(mn[v],t);last[u]f[u],f[u]t;}for(auto [u,t]:event[w]){if(e[u].size()Bs){int rlast[u];for(auto v:e[u]) rmin(r,f[v]);ans[u]max(0,r-t);}else{ans[u]max(0,min(last[u],mn[u])-t);}}}for(int i1;in;i) printf(%d\n,ans[i]);return 0;
}
