NOI批量评测 - 记录详情

In file included from /nix/gcc-13.3.0/include/c++/13.3.0/algorithm:61,
                 from /nix/gcc-13.3.0/include/c++/13.3.0/x86_64-unknown-linux-gnu/bits/stdc++.h:51,
                 from foo.cc:1:
In function 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = s*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(s, s)>]',
    inlined from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = s*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(s, s)>]' at /nix/gcc-13.3.0/include/c++/13.3.0/bits/stl_algo.h:1950:31,
    inlined from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = s*; _Compare = bool (*)(s, s)]' at /nix/gcc-13.3.0/include/c++/13.3.0/bits/stl_algo.h:4894:18,
    inlined from 'int main()' at foo.cc:112:13:
/nix/gcc-13.3.0/include/c++/13.3.0/bits/stl_algo.h:1859:32: warning: array subscript 17 is outside array bounds of 's [10]' [-Warray-bounds=]
 1859 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foo.cc: In function 'int main()':
foo.cc:7:2: note: at offset 204 into object 'a' of size 120
    7 | }a[maxn];
      |  ^
Expand

#	状态分数	耗时	内存占用

#1	Wrong Answer 0 读取到 0，应为 909667976。	2ms	404 KiB
#2	Wrong Answer 0 读取到 0，应为 984375007。	2ms	404 KiB
#3	Wrong Answer 0 读取到 0，应为 717773443。	2ms	404 KiB
#4	Time Exceeded 0	≥4101ms	≥404 KiB
#5	Time Exceeded 0	≥4101ms	≥404 KiB
#6	Time Exceeded 0	≥4101ms	≥404 KiB
#7	Time Exceeded 0	≥4100ms	≥404 KiB
#8	Time Exceeded 0	≥4100ms	≥404 KiB
#9	Time Exceeded 0	≥4100ms	≥276 KiB
#10	Time Exceeded 0	≥4101ms	≥320 KiB
#11	Time Exceeded 0	≥4101ms	≥404 KiB
#12	Time Exceeded 0	≥4101ms	≥408 KiB
#13	Time Exceeded 0	≥4101ms	≥412 KiB
#14	Time Exceeded 0	≥4101ms	≥408 KiB
#15	Time Exceeded 0	≥4101ms	≥404 KiB
#16	Time Exceeded 0	≥4101ms	≥404 KiB
#17	Time Exceeded 0	≥4100ms	≥404 KiB
#18	Time Exceeded 0	≥4100ms	≥404 KiB
#19	Time Exceeded 0	≥4001ms	≥404 KiB
#20	Time Exceeded 0	≥4101ms	≥404 KiB
#21	Time Exceeded 0	≥4101ms	≥404 KiB
#22	Time Exceeded 0	≥4101ms	≥404 KiB
#23	Time Exceeded 0	≥4000ms	≥404 KiB
#24	Time Exceeded 0	≥4101ms	≥404 KiB
#25	Time Exceeded 0	≥4101ms	≥404 KiB

#include<bits/stdc++.h>
const int maxn=10;
const long long mod=1e9+7;
using namespace std;
struct s{
    int u,v,w;
}a[maxn];
int n,m;
int C,T;
long long B=1,A;
bool cmp(s a,s b){
    return a.w<b.w ;
}
int fa[maxn];
int _smll=0;
int find(int x){
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}


int take[10];
struct node{
    int to,w,next;
}e[maxn<<1];
int head[maxn],cnt=0;
void add(int u,int v,int w){
    cnt++;
    e[cnt].to=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
int fg;
int vis[maxn];
void dfs2(int x,int now1,int sum){
    if(now1==n){
        if(sum==_smll)
            fg=1;
        return ;
    }
    if(fg) return ;
    for(int i=head[x]; i ;i=e[i].next){
        int to=e[i].to ;
        if(vis[to]) continue;
        vis[to]=1;
        dfs2(to,now1+1,sum+e[i].w );
        if(fg) return ;
        vis[to]=0;
    }
}
void solve(){
    memset(head,0,sizeof(head));
    cnt=0;
    for(int i=1;i<=m;i++){
        if(take[i]==1)
            add(a[i].u,a[i].v,a[i].w );
        if(take[i]==2)
            add(a[i].v,a[i].u,a[i].w );
        if(take[i]==3){
            add(a[i].u,a[i].v,a[i].w );
            add(a[i].v,a[i].u,a[i].w);
        }
    }
    fg=0;
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        vis[i]=1;
        dfs2(i,1,0);
        if(fg) A++;
    }
}
void dfs(int x){
    if(x==m+1){
        solve();
        return ;
    }
    else{
        for(int i=0;i<=3;i++){
            take[i]=i;
            dfs(x+1);
            take[i]=0;
        }
    }
}
long long gcd(long long A,long long B){
    if(B==0) return A;
    else return gcd(B,A%B);
}
long long cal(long long a,long long b ){
    long long ans=1,base=a;
    while(b){
        if(b&1) ans=ans*base%mod;
        base=base*base%mod;
        b=b/2;
    }
    return ans;
}
int main(){
    freopen("years.in","r",stdin);
    freopen("years.out","w",stdout);

    cin>>C>>T;
    while(T--){
        cin>>n>>m;
        A=0;
        B=1;
        for(int i=1;i<=m;i++){
            cin>>a[i].u>>a[i].v>>a[i].w ;
            B=B*4;
        }
        sort(a+1,a+1+m,cmp);
        for(int i=1;i<=n;i++)
            fa[i]=i;
        int res=0;
        _smll=0;
        for(int i=1;i<=m;i++){
            int xx=find(a[i].u );
            int yy=find(a[i].v );
            if(xx!=yy){
                fa[xx]=yy;
                res++;
                _smll+=a[i].w ;
                if(res==n-1) break;
            }
        }
        //minn tree

        dfs(1);
        // cout<<_smll<<endl;
        // cout<<A<<" "<<B<<endl;
    //    long long d=gcd(A,B);
    //    A=A/d;
    //    B=B/d;
        A=A%mod;
        B=B%mod;
        long long op=cal(B,mod-2);
        long long x=A*op%mod;
        x=x*mod%mod;
        cout<<x<<endl;
    }
    return 0;
}

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

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

0 Time Exceeded

代码

信息

还没有账户？

登录