oj.uz

Submission #561401

# Submission time Handle Problem Language Result Execution time Memory
561401 2022-05-12T18:40:39 Z AGE Deblo (COCI18_deblo) C++14
90 / 90
 241 ms 64544 KB 
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ll long long
using namespace std;
const int N=1e5+5,M=2e3+10,mod=100000000000031;
vector<int>adj[N];

long long  summ(long long  x,long long  y){
    return ((x%mod)+(y%mod))%mod;
}

long long  mult(long long  x,long long  y){
    return ((x%mod)*(y%mod))%mod;
}

ll dp[N][25],num[N],a[N],ans[N][25],xx[25];
int aa[N][25];

void dfs2(int node,int par){

    for(auto x:adj[node]){

        if(x==par)
            continue;

        dfs2(x,node);

    }

    for(auto x:adj[node])
        num[node]+=num[x];

    num[node]++;

}

void dfs(int node,int par){

    for(auto x:adj[node]){

        if(x==par)
            continue;

        dfs(x,node);

    }

    for(int j=0;j<=24;j++){

        if(aa[node][j]==1){

            for(auto x:adj[node]){

                if(x==par)
                    continue;

                dp[node][j]+=num[x]-dp[x][j];

            }

            if(adj[node].size()!=1||node==1)
                dp[node][j]++;

        }

        else
            for(auto x:adj[node])
                dp[node][j]+=dp[x][j];

    }


    if(adj[node].size()==1&&node!=1)
        for(int j=0;j<=24;j++)
            dp[node][j]=aa[node][j];

}

int n;
void dfs3(int node,int par){

    if(node!=1){

        for(int j=0;j<=24;j++)
            xx[j]=ans[par][j];

        for(int j=0;j<=24;j++)

            if(aa[par][j]==1)
                xx[j]-=(num[node]-dp[node][j]);

            else
                xx[j]-=dp[node][j];


        for(int j=0;j<=24;j++){

            if(aa[node][j]==1)
                ans[node][j]+=(n-num[node])-xx[j];

            else
                ans[node][j]+=xx[j];


        }

        for(int j=0;j<=24;j++)
            ans[node][j]+=dp[node][j];

    }

    for(auto x:adj[node]){

        if(x==par)
            continue;

        dfs3(x,node);

    }
}
main()
{

    cin>>n;

    for(int i=1;i<=n;i++){

        int x;
        cin>>x;
        a[i]=x;

        for(int j=0;j<=24;j++)
            if(x&(1<<j))
                aa[i][j]=1;

    }



    for(int i=1;i<n;i++){

        int x,y;
        cin>>x>>y;

        adj[x].pb(y);
        adj[y].pb(x);

    }

    dfs2(1,0);
    dfs(1,0);

    for(int j=0;j<=24;j++)
        ans[1][j]=dp[1][j];

    dfs3(1,0);

    ll answer=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=24;j++)

            if(ans[i][j]==0)
                continue;
            else
                answer+=ans[i][j]*(1<<j);

    ll sum=0;

    for(int i=1;i<=n;i++)
        sum+=a[i];

    answer-=sum;
    answer/=2;
    answer+=sum;

    cout<<answer<<endl;

    return 0;
}

Compilation message

deblo.cpp:7:32: warning: overflow in conversion from 'long int' to 'int' changes value from '100000000000031' to '276447263' [-Woverflow]
    7 | const int N=1e5+5,M=2e3+10,mod=100000000000031;
      |                                ^~~~~~~~~~~~~~~
deblo.cpp:123:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  123 | main()
      | ^~~~

Subtask #1
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 4 ms 3156 KB Output is correct
5 Correct 4 ms 3156 KB Output is correct
6 Correct 180 ms 64468 KB Output is correct
7 Correct 189 ms 64544 KB Output is correct
8 Correct 227 ms 57584 KB Output is correct
9 Correct 195 ms 57012 KB Output is correct
10 Correct 241 ms 56260 KB Output is correct