CE 求助
查看原帖
CE 求助
542128
liyixin0514楼主2024/12/19 20:29

rt,萌新不是很会交互题,求助。编译错误信息放二楼。

提前拜谢大佬/bx/bx/bx

#include<bits/stdc++.h>
#include<vector>
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
constexpr int N=1e3+7;
typedef vector<int> vi;
typedef vector<vi> vvi;
int n;
void build(std::vector<std::vector<int> > b);
#ifdef LOCAL
void build(vvi b) {
    rep(i,0,n-1) if(b[i][i]) return puts("loop!"), void(0);
    rep(i,0,n-1) rep(j,0,n-1) if(b[i][j]!=b[j][i]) return puts("diffrent!"), void(0);
    rep(i,0,n-1) rep(j,i+1,n-1) if(b[i][j]) pf("%d %d\n",i,j);
}
#endif
int fa[N],fa2[N];
int find(int u) { return fa[u]==u ? u : fa[u]=find(fa[u]); }
int find2(int u) { return fa2[u]==u ? u : fa2[u]=find2(fa2[u]); }
vector<int> loop[N];
int construct(vvi p) {
    n=p.size();
    // pf("n = %d\n",n);
    rep(i,0,n-1) rep(j,i+1,n-1) if(p[i][j]==3) return 0;
    rep(i,0,n-1) fa[i]=i, fa2[i]=i;
    rep(i,0,n-1) rep(j,i+1,n-1) {
        if(p[i][j]==1) {
            int fi=find(i), fj=find(j);
            if(fi!=fj) fa[fi]=fj;
            // pf("merge1 %d %d\n",i,j);
        }
    }
    rep(i,0,n-1) rep(j,i+1,n-1) {
        if(p[i][j]==2) {
            int fi=find(i), fj=find(j);
            if(fi==fj) return 0;
            fi=find2(find(i)), fj=find2(find(j));
            if(fi!=fj) fa2[fi]=fj;
            // pf("merge2 %d %d\n",fi,fj);
        }
    }
    rep(i,0,n-1) rep(j,i+1,n-1) {
        if(p[i][j]==0) {
            int fi=find2(find(i)), fj=find2(find(j));
            if(fi==fj) return 0;
        }
    }
    // puts("ok1");
    vvi b;
    b.resize(n);
    rep(i,0,n-1) b[i].resize(n);
    rep(i,0,n-1) {
        if(fa[i]==i) {
            int f=find2(i);
            loop[f].push_back(i);
            // pf("%d %d\n",f,i);
        }
    }
    // puts("ok2");
    rep(i,0,n-1) {
        if(fa[i]!=i) b[i][fa[i]] = b[fa[i]][i] = 1;
        rep(j,1,(int)loop[i].size()-1) b[loop[i][j-1]][loop[i][j]] = b[loop[i][j]][loop[i][j-1]] = 1;
        if(loop[i].size()>1) b[loop[i][0]][loop[i].back()] = b[loop[i].back()][loop[i][0]] = 1;
    }
    // puts("ok3");
    build(b);
    return 1;
}
#ifdef LOCAL
int main() {
    freopen("in.txt","r",stdin);
    freopen("my.out","w",stdout);
    int x;
    sf("%d",&x);
    vvi tmp;
    tmp.resize(x);
    rep(i,0,x-1) tmp[i].resize(x);
    rep(i,0,x-1) rep(j,0,x-1) sf("%d",&tmp[i][j]);
    pf("ans = %d\n",construct(tmp));
}
#endif
2024/12/19 20:29
加载中...