SPJ有误
查看原帖
SPJ有误
527303
tybbs不是SCATZ楼主2023/11/26 21:48

SPJ并没有判定 “每两棵树的边集在超正方体中所对应的边集不交,即超正方体中的每条边最多包含于一棵树中”

正确的如下

#include<bits/stdc++.h>
#include"testlib.h"
using namespace std;
int n,k,x[16],y[16],p[65536];
bool vis[65536];
map<pair<int,int>,bool>mp;
int main(int argc,char *argv[])
{
    registerTestlibCmd(argc,argv);
    n=inf.readInt();
    for(int i=0;i<n;++i)x[i]=inf.readInt(),y[i]=inf.readInt();
    k=ouf.readInt(0,1<<(n-1));
    ouf.readEoln();
    for(int i=0;i<k;++i)
    {
        memset(vis,false,sizeof(vis));
        for(int j=0;j<=n;++j)
        {
            p[j]=ouf.readInt(0,(1<<n)-1);
            if(vis[p[j]])quitf(_wa,"Repetitive node!");
            vis[p[j]]=true;
            if(j!=n)ouf.readSpace();
        }
        for(int j=0;j<n;++j)
        {
            int u=p[x[j]],v=p[y[j]];
            if(u>v)swap(u,v);
            if(mp.find(make_pair(u,v))!=mp.end())quitf(_wa,"Repetitive edge!");
            mp[make_pair(u,v)]=true;
            if(__builtin_popcount(u^v)!=1)quitf(_wa,"Invalid edge!");
        }
    }
    if(!k)quitf(_wa,"No trees tiled!");
    else if(k==1)quitp(0.7/(1<<(n-1)),"1 tree tiled correctly!");
    else if(k<(1<<(n-1)))quitp(0.7*k/(1<<(n-1)),"%d trees tiled correctly!",k);
    quitf(_ok,"Your answer is correct!");
    return 0;
}
2023/11/26 21:48
加载中...