为什么改了这行代码 68pts wa --> AC?
查看原帖
为什么改了这行代码 68pts wa --> AC?
507348
__vector__楼主2024/6/17 11:39

我一直卡在 68pts,看到警示帖说是退栈写挂了。

然后我就把退栈改成了 OI-wiki 的写法

然后对了。

但我并没有看出哪里有区别,思想都是把除了 uu 以外栈中其他元素清除。

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]++;
}  

求助。

2024/6/17 11:39
加载中...