/ tabris /

记录详情

Runtime Error

/in/foo.cc: In function 'void dfs(int, int)':
/in/foo.cc:16:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<t[u].size(); i++) {
                   ~^~~~~~~~~~~~
/in/foo.cc: In function 'void sum01(int, int)':
/in/foo.cc:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<t[u].size(); i++) {
                   ~^~~~~~~~~~~~
/in/foo.cc: In function 'void solve(int, int)':
/in/foo.cc:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<t[u].size(); i++) {
                   ~^~~~~~~~~~~~
# 状态 耗时 内存占用
#1 Wrong Answer 56ms 6.855 MiB
#2 Runtime Error 66ms 35.754 MiB
#3 Wrong Answer 3ms 2.574 MiB
#4 Wrong Answer 5ms 2.695 MiB
#5 Wrong Answer 4ms 2.699 MiB
#6 Wrong Answer 6ms 2.695 MiB
#7 Wrong Answer 206ms 25.496 MiB
#8 Wrong Answer 33ms 6.945 MiB
#9 Wrong Answer 207ms 23.895 MiB
#10 Wrong Answer 221ms 29.203 MiB

代码

#include <bits/stdc++.h>
#define nmax 100005
#define m 1000000007

using namespace std;
int n,ie=-1;
vector <int> t[nmax];
int x[nmax],ans[nmax]={0};
int n0[nmax][31],n1[nmax][31];  //最多有31位

struct edge{
    int v,w;
}e[nmax];

void dfs(int fa,int u){
    for (int i=0; i<t[u].size(); i++) {
        edge ue=e[ t[u][i] ];
        if(ue.v==fa) continue;
        x[ue.v]=x[u]^ue.w;
        dfs(u,ue.v);
    }
}

void sum01(int fa,int u){  //统计每一个子树每一位的01个数
    for (int i=0; i<31; i++) {
        if( (1<<i) & x[u] )  {  n0[u][i]=0; n1[u][i]=1; }
        else                 {  n0[u][i]=1; n1[u][i]=0; }
    }
    for (int i=0; i<t[u].size(); i++) {
        int v=e[ t[u][i] ].v;
        if(v==fa) continue;
        sum01(u,v);
        for (int i=0; i<31; i++) { n0[u][i]+=n0[v][i]; n1[u][i]+=n1[v][i]; }
    }
}

void solve(int fa,int u){  //算贡献求解  别忘了取模quq
    int tmp0[31],tmp1[31];
    for (int i=0; i<31; i++) { tmp0[i]=n0[u][i]; tmp1[i]=n1[u][i]; }
    for (int i=0; i<t[u].size(); i++) {
        int v=e[ t[u][i] ].v;
        if(v==fa) continue;
        solve(u,v);
        for (int i=0; i<31; i++) { tmp0[i]-=n0[v][i];  tmp1[i]-=n1[v][i];  }

        //for (int i=0; i<31; i++) { cout<<u<<' '<<tmp0[i]<<' '<<tmp1[i]<<endl;  }

        //按位算贡献,得出ans
        for (int i=0; i<31; i++) {
            int c=(1<<i)%m;
            int tmp=n0[v][i]*tmp1[i]+n1[v][i]*tmp0[i];
            tmp%=m;
            ans[u]+=( (tmp*c)%m );
            ans[u]%=m;
           // printf("tmp=%d,u=%d,ans[%d]=%d\n",tmp,u,u,ans[u]);
        }
        ans[u]+=ans[v];
        ans[u]%=m;
    }
}

int main(){

    //freopen("owo.txt","r",stdin);
    //freopen("quq.txt","w",stdout);

    cin>>n;
    int a,b,c;
    for (int i=1; i<n; i++) {
        scanf("%d%d%d",&a,&b,&c);
        ie++;
        t[a].push_back(ie);
        e[ie].v=b;
        e[ie].w=c;
    }
    x[1]=0;
    dfs(0,1);
    sum01(0,1);
    solve(0,1);

    for (int i=1; i<=n; i++) {
            cout<<ans[i]<<endl;
       // for (int j=0; j<31; j++) cout<<n0[i][j]<<' '<<n1[i][j]<<endl;
    }

    return 0;
}

信息

递交者
类型
递交
语言
C++
递交时间
2019-06-11 14:14:01
评测时间
2019-06-11 14:14:01
评测机
分数
0
总耗时
813ms
峰值内存
35.754 MiB