比赛 |
4043级NOIP2022欢乐赛6th |
评测结果 |
WAAAEAAAAWAAEAAAAAAA |
题目名称 |
BLO-Blockade |
最终得分 |
80 |
用户昵称 |
ZRQ |
运行时间 |
0.614 s |
代码语言 |
C++ |
内存使用 |
4.21 MiB |
提交时间 |
2022-11-18 20:00:20 |
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005,M=500005;
int n,m,hd[N],e[M],nt[M],idx,df[N],lw[N],clk,siz[N];
ll ans[N];
char ch;
inline void add(int x,int y){nt[++idx]=hd[x],hd[x]=idx,e[idx]=y;}
inline void read(int &x){x=0;ch=getchar();while(ch<48||ch>57)ch=getchar();while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return ;}
void tarjan(int cur)
{
int res=0;
siz[cur]=1;
df[cur]=lw[cur]=++clk;
for(int i=hd[cur];i;i=nt[i])
{
if(!df[e[i]])
{
tarjan(e[i]);
siz[cur]+=siz[e[i]];
lw[cur]=min(lw[cur],lw[e[i]]);
if(lw[e[i]]>=df[cur]) ans[cur]+=siz[e[i]]*res,res+=siz[e[i]];
}
lw[cur]=min(lw[cur],df[e[i]]);
}
ans[cur]+=(n-res-1)*res;
return ;
}
int main()
{
freopen("BLO.in","r",stdin);
freopen("BLO.out","w",stdout);
read(n),read(m);
for(int i=1,x,y;i<=m;++i) read(x),read(y),add(x,y),add(y,x);
for(int i=1;i<=n;++i) if(!df[i]) tarjan(i);
for(int i=1;i<=n;++i) printf("%lld\n",(ans[i]+n-1)<<1);
return 0;
}