1 条题解
-
0
洛谷题解
#include<bits/stdc++.h> using namespace std; # define ll long long # define read read1<ll>() # define Type template<typename T> Type T read1(){ T t=0;char k;bool vis=0; do (k=getchar())=='-'&&(vis=1);while('0'>k||k>'9'); while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar(); return vis?-t:t; } # define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout) struct B{ int x,y; B(int _x=0,int _y=0):x(_x),y(_y){} bool operator <(const B &t)const{return x+y==t.x+t.y?y<t.y:x+y<t.x+t.y;} bool operator ==(const B &t)const{return x==t.x&&y==t.y;} }; map<int,int>U[100015],S[100015]; struct E{int u,t;}G[400005]; int f[100005],s,m,tot,dis[100005][2],q[200005]; bool r[200005];vector<B>tem; void add(int u,int v){ G[++tot].u=v;G[tot].t=f[u];f[u]=tot; G[++tot].u=u;G[tot].t=f[v];f[v]=tot; } int main(){q[0]=1;r[0]=0; for(int T=read;T--;){ s=read,m=read;tot=0; memset(f,0,s+1<<2); memset(dis,-1,s+1<<3); for(int i=1;i<=m;++i)add(read,read); for(int i=0;i<=s+5;++i)S[i].clear(),U[i].clear(); dis[1][0]=0; for(int i=0,j=1;i!=j;++i){ int n=q[i]; for(int x=f[n];x;x=G[x].t) if(!~dis[G[x].u][!r[i]]){ r[j]=!r[i];q[j]=G[x].u;++j; dis[G[x].u][!r[i]]=dis[n][r[i]]+1; } }int ans=0; if(!~dis[1][1])ans=s-1; else if(dis[1][1]==1)ans=s; else{tem.clear(); for(int i=2;i<=s;++i){ int x=dis[i][0],y=dis[i][1]; if(y>x)swap(x,y); ++S[x][y];tem.push_back(B(x,y)); }S[dis[1][1]][0]=1; sort(tem.begin(),tem.end()); B v(114514,-1); for(int i=0;i<tem.size();++i){ if(v==tem[i])continue; v=tem[i]; int cnt=S[v.x][v.y],h=S[v.x-1][v.y-1],p=U[v.x+1][v.y-1]; if(!h)ans+=max(cnt-p,0)+(v.y+1<v.x?U[v.x][v.y]=cnt:cnt+1>>1); else if(!p)ans+=cnt; else ans+=max(cnt-p,0)+(v.y+1<v.x?U[v.x][v.y]=min(cnt,p):min(cnt,p)+1>>1); } } printf("%d\n",ans); } return 0;///test }
- 1
信息
- ID
- 6310
- 时间
- 1000ms
- 内存
- 250MiB
- 难度
- 7
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者