关于 NOIP T2 数据
  • 板块学术版
  • 楼主tanghg
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/11/19 21:37
  • 上次更新2023/11/20 12:25:54
查看原帖
关于 NOIP T2 数据
692647
tanghg楼主2023/11/19 21:37

请问一下各位大佬,洛谷的数据是不是除了自环以外没有个数大于 2 的负环了啊,我的一个代码样例 4 都没过但是洛谷 AC 了。

这是我的代码:

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll c,t;
struct query{
    char op;
    ll x,y;
}q[MAXN];
ll n,m;
void init(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;++i){
        cin>>q[i].op;
        if(q[i].op=='+'||q[i].op=='-'){
            scanf("%lld%lld",&q[i].x,&q[i].y);
        }else{
            scanf("%lld",&q[i].x);
        }
    }
}
namespace Task5_6{
    pair<ll,ll>f[MAXN];
    vector<ll>adj[MAXN];
    bool vis[MAXN];
    ll ans;
    void dfs(ll u){
        for(auto v:adj[u]){
            if(vis[v]){
                continue;
            }
            vis[v]=true;
            ans++;
            dfs(v);
        }
    }
    void Do(){
        ans=0;
        memset(vis,false,sizeof(vis));
        for(int i=0;i<MAXN;++i){
            f[i]={i,1};
            adj[i].clear();
        }
        for(int i=1;i<=m;++i){
            if(q[i].op=='+'){
                ll u=q[i].x,v=q[i].y;
                f[u]=f[v];
            }else if(q[i].op=='-'){
                ll u=q[i].x,v=q[i].y;
                f[u]=f[v];
                f[u].second*=-1;
            }else if(q[i].op=='T'){
                ll u=q[i].x,v=n+1;
                f[u]=f[v];
            }else if(q[i].op=='F'){
                ll u=q[i].x,v=n+2;
                f[u]=f[v];
            }else if(q[i].op=='U'){
                ll u=q[i].x,v=n+3;
                f[u]=f[v];
            }

        }
        for(int i=1;i<=n;++i){
            adj[f[i].first].push_back(i);
        }
        for(int i=1;i<=n;++i){
            if(f[i].first==n+3){
                vis[i]=true;
                ans++;
                dfs(i);
            }
            if(f[i].first==i&&f[i].second==-1){
                vis[i]=true;
                ans++;
                dfs(i);
            }
        }
        printf("%lld\n",ans);
    }
}
int main(){
    freopen("tribool.in","r",stdin);
    freopen("tribool.out","w",stdout);
    scanf("%lld%lld",&c,&t);
    if(c<=6123123123123){
        while(t--){
            init();
            Task5_6::Do();
        }
    }
    return 0;
}
2023/11/19 21:37
加载中...