我一直卡在 68pts,看到警示帖说是退栈写挂了。
然后我就把退栈改成了 OI-wiki 的写法
然后对了。
但我并没有看出哪里有区别,思想都是把除了 u 以外栈中其他元素清除。
68 分
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int T;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
const int maxn=1e5+5;
const int maxm=2e5+5;
int n,m;
vector<int> g[maxn],h[maxn*2];
int dfn[maxn],low[maxn],dfncnt;
int stk[maxn],top;
int sqcnt;
int val[maxn*2];
int tt;
void tarjan(int u){
tt++;
dfn[u]=low[u]=++dfncnt;
stk[++top]=u;
val[u]=-1;
for(int& v:g[u]){
if(!dfn[v]){
tarjan(v);
ckmn(low[u],low[v]);
if(low[v]==dfn[u]){
sqcnt++;
while(stk[top]^u){
h[stk[top]].emplace_back(sqcnt);
h[sqcnt].emplace_back(stk[top]);
val[sqcnt]++;
top--;
}
h[sqcnt].emplace_back(u);
h[u].emplace_back(sqcnt);
val[sqcnt]++;
}
}else{
ckmn(low[u],dfn[v]);
}
}
}
ll ans=0;
int siz[maxn*2];
void dfs(int u,int _fa){
siz[u]=(u<=n);
for(int& v:h[u]){
if(v^_fa){
dfs(v,u);
ans+=2ll*ll(val[u])*ll(siz[u])*ll(siz[v]);
siz[u]+=siz[v];
}
}
ans+=2ll*(ll)val[u]*ll(tt-siz[u])*ll(siz[u]);
}
void solve(){
scanf("%d%d",&n,&m);
sqcnt=n;
FOR(i,1,m){
int u,v;
scanf("%d%d",&u,&v);
g[u].emplace_back(v);
g[v].emplace_back(u);
}
FOR(i,1,n){
if(!dfn[i]){
tt=0;
tarjan(i);
dfs(i,0);
}
}
printf("%lld\n",ans);
}
int main()
{
T=1;
while(T--){
solve();
}
return 0;
}
100pts:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int T;
template<class T>
void ckmx(T& a,T b){
a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
a=min(a,b);
}
const int maxn=1e5+5;
const int maxm=2e5+5;
int n,m;
vector<int> g[maxn],h[maxn*2];
int dfn[maxn],low[maxn],dfncnt;
int stk[maxn],top;
int sqcnt;
int val[maxn*2];
int tt;
void tarjan(int u){
tt++;
dfn[u]=low[u]=++dfncnt;
stk[++top]=u;
val[u]=-1;
for(int& v:g[u]){
if(!dfn[v]){
tarjan(v);
ckmn(low[u],low[v]);
if(low[v]==dfn[u]){
sqcnt++;
for(int dlt=0;dlt!=v;top--){
dlt=stk[top];
h[stk[top]].emplace_back(sqcnt);
h[sqcnt].emplace_back(stk[top]);
val[sqcnt]++;
}
h[sqcnt].emplace_back(u);
h[u].emplace_back(sqcnt);
val[sqcnt]++;
}
}else{
ckmn(low[u],dfn[v]);
}
}
}
ll ans=0;
int siz[maxn*2];
void dfs(int u,int _fa){
siz[u]=(u<=n);
for(int& v:h[u]){
if(v^_fa){
dfs(v,u);
ans+=2ll*ll(val[u])*ll(siz[u])*ll(siz[v]);
siz[u]+=siz[v];
}
}
ans+=2ll*(ll)val[u]*ll(tt-siz[u])*ll(siz[u]);
}
void solve(){
scanf("%d%d",&n,&m);
sqcnt=n;
FOR(i,1,m){
int u,v;
scanf("%d%d",&u,&v);
g[u].emplace_back(v);
g[v].emplace_back(u);
}
FOR(i,1,n){
if(!dfn[i]){
tt=0;
tarjan(i);
dfs(i,0);
}
}
printf("%lld\n",ans);
}
int main()
{
T=1;
while(T--){
solve();
}
return 0;
}
唯一的差别在于第 39~44 行的
while(stk[top]^u){
h[stk[top]].emplace_back(sqcnt);
h[sqcnt].emplace_back(stk[top]);
val[sqcnt]++;
top--;
}
改成了
for(int dlt=0;dlt!=v;top--){
dlt=stk[top];
h[stk[top]].emplace_back(sqcnt);
h[sqcnt].emplace_back(stk[top]);
val[sqcnt]++;
}
求助。