NOIP2023 tribool

SnowTrace · 2023-11-20 19:06:40 · 题解

规定 T 为 1，F 为 -1，U 为 0。

我们考虑维护结果。

在最终 n 个数的值要么是定值，要么可以写成 ka_j 的形式，其中 -1\leq k \leq 1。

如果最终有出来的结果有 a_i = ka_j 我们把 i 和 j 连上，边权是 k，然后我们获得一颗基环树。

假设树上某个点是个定值（其实就相当于这个联通块是一颗内向树），我们可以直接遍历联通块赋值。

否则这个联通块内的点的答案还不能直接确定。

考虑这个基环树上的环：

假设环上边乘积是 -1，也就是说 a_i = -a_i，从而一整个联通块都是 U。

否则，随便赋值，也就是可以赋值成全部都不是 U 的形态。

代码仅供参考。

#include<bits/stdc++.h>
using namespace std;
int fl[200005],val[200005];
int n,m;
int in[200005],out[200005],ans[200005],vis[200005],pp[200005],ss[200005],fa[200005],used[200005];
int sz[200005];
vector<pair<int,int> >p[200005],p1[200005];
int find(int x){
    if(fa[x] == x)return x;
    return fa[x] = find(fa[x]);
}void merge(int x,int y){
    int a = find(x),b = find(y);
    if(b == a)return;
    fa[b] = a;sz[a]+=sz[b];sz[b] = 0;
}
void dfs(int now,int val){vis[now] = 1;
    ans[now] = val;
    for(int i =0;i<p1[now].size();i++){
        dfs(p1[now][i].first,p1[now][i].second*val);
    }return;
}int pro = 1,ok = 0;
void dfs1(int now){
    if(vis[now] == 1){
        if(pp[now]!=pro)ok = 1;
        return;
    }vis[now] =1;pp[now] = pro;
    for(int i =0;i<p[now].size();i++){
        pro = pro*p[now][i].second;
        dfs1(p[now][i].first);
    }
}
void solve(){
    cin >> n >> m;
    for(int i =1;i<=n;i++)fl[i] = 1,val[i] = i,in[i] = 0,out[i] = 0,ans[i] = -2,vis[i] = 0,ss[i] = 0,sz[i] = 1;
    for(int i =1;i<=n;i++)fa[i] = i,used[i] = 0;
    for(int i = 1;i<=n;i++)p[i].clear(),p1[i].clear();
    for(int i =1;i<=m;i++){
        char c;cin >> c;
        if(c == '-'){
            int x,y;cin >> x >> y;
            if(fl[y] == 0){
                fl[x] = 0;val[x] = -val[y];
            }else{
                fl[x] = -fl[y],val[x] = val[y];
            }
        }if(c == '+'){
            int x,y;cin >> x >> y;
            val[x] = val[y],fl[x] = fl[y];
        }if(c == 'T'){
            int x;cin >> x;
            fl[x] = 0,val[x] = 1;
        }if(c == 'F'){
            int x;cin >> x;
            fl[x] = 0,val[x] = -1;
        }if(c == 'U'){
            int x;cin >> x;
            fl[x]  =0,val[x] = 0;
        }
    }for(int i = 1;i<=n;i++){
        if(fl[i]!=0){
            p1[val[i]].push_back({i,fl[i]});
            p[i].push_back({val[i],fl[i]});merge(val[i],i);
        }
    }for(int i = 1;i<=n;i++){
        if(fl[i] == 0){
                used[find(i)] = 1;
            dfs(i,val[i]);
        }
    }int tot = 0;
    for(int i= 1;i<=n;i++){
        if(!used[find(i)]){used[find(i)] = 1;
            pro =  1,ok = 0;
            dfs1(i);
            tot+=ok*sz[find(i)];
        }
    }
    for(int i = 1;i<=n;i++)if(ans[i] == 0)tot++;
    cout << tot << endl;
}int id;
signed main(){
 //   freopen("tribool.in","r",stdin);
 //   freopen("tribool.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> id;
    int t;cin >> t;
    while(t--){
        solve();
    }
    return 0;
}