为什么线性做法会被卡
查看原帖
为什么线性做法会被卡
684254
Rain_chr楼主2023/11/28 12:58

我是有地方写假了吗?为什么只有80分?

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int fa[N];
vector<int> a[N];
pair<int,int> now[N];
int col[N];
int cnt;
int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
bool dfs(int x)
{
    cnt++;
    bool op=0;
    for(int to:a[x])
    {
        if(col[to]==-1) 
        {
            col[to]=col[x]^1;
            op|=dfs(to);
        }
        else if(col[to]==col[x]) op=1;
    }
    return op;
}
bool can[N];
void color(int x)
{
    can[x]=1;
    for(int to:a[x])
        if(!can[to]) 
            color(to);
}
void run()
{
    int n,m;
    cin>>n>>m;
    int k=(n+3);
    for(int i=1;i<=2*k;i++)
    {
        fa[i]=i;
        a[i].clear();
        now[i]=make_pair(i,0);
        can[i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        char ch;
        cin>>ch;
        if(ch=='+'||ch=='-')
        {
            int x,y;
            cin>>x>>y;
            now[x]=now[y];
            now[x].second^=(ch=='-');
        }
        else
        {
            int x;
            cin>>x;
            if(ch=='T') now[x]=now[n+1];
            if(ch=='F') now[x]=now[n+2];
            if(ch=='U') now[x]=now[n+3];
        }
    }
    fa[find(n+1)]=find(n+2+k);
    fa[find(n+2)]=find(n+1+k);
    fa[find(n+3)]=fa[find(n+3+k)];
    for(int i=1;i<=n;i++)
    {
        if(now[i].second) fa[find(i)]=find(now[i].first+k);
        else fa[find(i)]=find(now[i].first);
    }
    for(int i=1;i<=k;i++)
    {
        a[find(i)].push_back(find(i+k));
        a[find(i+k)].push_back(find(i));
    }
    memset(col,-1,sizeof(col));
    for(int i=1;i<=k;i++)
    {
        if(col[find(i)]!=-1) continue;
        col[i]=1;
        if(dfs(find(i)))
            color(find(i));
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans+=(can[find(i)]|can[find(i+k)]);
    cout<<ans<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int c,t;
    cin>>c>>t;
    while(t--)
        run();
    return 0;
}
2023/11/28 12:58
加载中...