NOI批量评测 - 记录详情

foo.cc: In function 'long long int dfs(long long int, long long int)':
foo.cc:85:1: warning: no return statement in function returning non-void [-Wreturn-type]
   85 | }
      | ^
foo.cc: In function 'long long int work(long long int)':
foo.cc:114:1: warning: control reaches end of non-void function [-Wreturn-type]
  114 | }
      | ^
foo.cc: In function 'long long int dfs(long long int, long long int)':
foo.cc:76:12: warning: infinite recursion detected [-Winfinite-recursion]
   76 | inline int dfs(int x,int fa)
      |            ^~~
foo.cc:82:12: note: recursive call
   82 |         dfs(y,x);
      |         ~~~^~~~~
Expand

#	状态分数	耗时	内存占用

#1	Time Exceeded 0	≥4100ms	≥404 KiB
#2	Time Exceeded 0	≥4101ms	≥320 KiB
#3	Time Exceeded 0	≥4100ms	≥404 KiB
#4	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#5	Time Exceeded 0	≥4001ms	≥404 KiB
#6	Time Exceeded 0	≥4101ms	≥404 KiB
#7	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#8	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#9	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#10	Wrong Answer 0 Standard answer longer than user output.	1ms	316 KiB
#11	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#12	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#13	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#14	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#15	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#16	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#17	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#18	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#19	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#20	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#21	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#22	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#23	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#24	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB
#25	Wrong Answer 0 Standard answer longer than user output.	1ms	404 KiB

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;

int n,m,c,T;
typedef pair<int,int> pii;
#define mp(a,b) make_pair(a.b)
#define fi first
#define se second
int head[7],ver[505],nxt[505],tot=0;
inline void add(int x,int y)
{
    ver[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
struct node
{
  int x,y,z;
}edge[20];

int fa[22],zhi[22];

inline int find(int x)
{
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
int ans=0,res=0;
inline void kruskal()
{
    ans=0;
    int cnt=n;//cout<<" "<<cnt<<endl;
    for(int i=1;i<=n;i++) fa[i]=i,zhi[i]=1;
    for(int i=1;i<=m;i++)
    {
        int fx=find(edge[i].x),fy=find(edge[i].y);
        if(fx!=fy) {
            cnt--;

            ans+=edge[i].z;
            //cout<<ans<<endl;
            if(zhi[fx]<zhi[fy]) swap(fx,fy);
            fa[fy]=fx;
            zhi[fx]+=zhi[fy];
            //add(edge[i].x,edge[i].y,edge[i].z);
            //add(edge[i].y,edge[i].x,edge[i].z);
        }

        if(cnt==1) return;
    }
}




inline int ksm(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

inline int inv(int x)
{
    return ksm(x,mod-2);
}
int siz[22];

inline int dfs(int x,int fa)
{
    siz[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i];
        if(y==fa) continue;
        dfs(y,x);
        siz[x]+=siz[y];
    }
}

int bj[20];

inline int work(int s)
{
    int ret=0;
    tot=0;
    memset(head,0,sizeof head);
    for(int i=0;i<m;i++){
        if((s>>i)&1)
        {
 //           p[++totp]=edge[i];
            int px=edge[i+1].x,py=edge[i+1].y;
            //cout<<bj<<endl;
            if(bj[i+1]==1) add(px,py),add(py,px);
            else if(bj[i+1]==2) add(px,py);
            else if(bj[i+1]==3) add(py,px);
            if(bj[i+1]!=4) ret+=edge[i+1].z;
        }
    }
    //cout<<ret<<" "<<ans<<endl;
    if(ret!=ans) return 0;
    for(int i=1;i<=n;i++){
        dfs(i,0);
        //cout<<i<<"   d";
        if(siz[i]==n) return 1;
    }

}




inline void dfsdfs(int st)
{
    if(st>m)
    {
        int op=0;
        for(int i=0;i<(1<<m);i++)
        {
            if(__builtin_popcount(i)==n-1) op|=work(i);
            //cout<<i<<" "<<op<<endl;

        }
        res+=op;
        return;
    }
    for(int i=1;i<=4;i++)
    {
        bj[st]=i;
        dfsdfs(st+1);
    }
}










inline void solve0()
{
    kruskal();
    //cout<<ans<<endl;
    res=0;
    dfsdfs(1);
    //cout<<res*ksm(2,(m-n+1))%mod<<endl;
    cout<<res*ksm(2,(m-n+1))%mod*inv(ksm(4,m))%mod<<"\n";
}

signed main()
{
    freopen("years.in","r",stdin);
    freopen("years.out","w",stdout);
    cin>>c>>T;
    while(T--)
    {
        cin>>n>>m;//cout<<n<<"\n";
        for(int i=1;i<=m;i++)
        {
            cin>>edge[i].x>>edge[i].y>>edge[i].z;
        }
        if(m<=6)solve0();
       // else if(c==4||c==5||c==6) solveB();
    }


    return 0;
}

递交者: SXJ-0004
题目: NOISX2025GFE NOISX2025GFE
比赛: 【官方数据 XJ】联合省选 2025 批量测试
语言: C++14(O2)
代码长度: 2.9 KiB
递交时间: 2025-3-6 12:55:41
评测时间: 2025-3-6 16:26:43

分数: 0
总耗时: ≥20428ms
峰值时间: ≥4101ms
峰值内存: ≥404 KiB

0 Time Exceeded

代码

信息

0 Time Exceeded

代码

信息

还没有账户？

登录