HackerEarth Weak nodes problem solution

In this HackerEarth Weak nodes problem solution You are given N nodes with the following information:

The nodes are connected by M bidirectional edges.

Each node has a value Vi associated with it.

A node is called a weak node if the connections between some other nodes are broken when that node is deleted and any alternate connections are not present.

Write a program to tell the number of subsets from all the possible subsets of weak nodes, which on getting their values multiplied gives a number which is divisible by all primes less than 25.

Since the answer can be large, print the answer Modulo 10^9 + 7.

HackerEarth Weak nodes problem solution.

#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
#define ll long long
ll n, m, vis[500100];
vector<ll> v[500100];
ll disc[500100], low[500100], power[500100], tim=0;
vector<ll> ap;
ll isap[500100]={0};
void solve(ll x, ll prev){
    vis[x]=1;
    disc[x]=low[x]=++tim;
    int child=0;
    for(int i=0; i<v[x].size(); i++){
        if(v[x][i] != prev){
            if(!vis[v[x][i]]){
                child++;
                solve(v[x][i], x);
                low[x] = min(low[x], low[v[x][i]]);
                if(prev == -1 && child > 1 && !isap[x]){
                    isap[x]=1;
                    ap.push_back(x);
                }           
                else if(prev != -1 && low[v[x][i]] >= disc[x] && !isap[x]){
                    isap[x]=1;
                    ap.push_back(x);
                }
            }
            else
                low[x] = min(low[x], disc[v[x][i]]);
        }
    }
}
 
ll POWER(ll a, ll b, ll mod)
{
        ll ret = 1 ;
        while(b)
        {
                if(b & 1 ) ret = ret*a % mod;
                a = a*a % mod;
                b >>= 1 ;
        }
        return ret;
}
 
int main(){
    cin>>n>>m;
    ll i, j, k;
    for(i=1; i<=n; i++)
        cin>>power[i];
    for(i=0; i<m; i++){
        ll x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1; i<=n; i++){
        if(!vis[i])
            solve(i,-1);
    }
    ll arr[9]={2, 3, 5, 7, 11, 13, 17, 19, 23};
    ll f[600]={0};
    for(i=0; i<ap.size(); i++){
        ll temp=0;
        for(j=0; j<9; j++)  
            if(power[ap[i]]%arr[j] == 0)
                temp|=(1<<j);
        f[temp]++;  
    }
    for(i=0; i<512; i++){
        f[i] = (POWER(2, f[i], MOD)-1+MOD)%MOD;
    }
    ll dp[2][10000]={0};
    ll c=1, p=0;
    for(i=0; i<512; i++){
        ll temp=f[i];
        for(j=0; j<512; j++)
            dp[c][j] = dp[p][j];    
        for(j=0; j<512; j++){
            dp[c][j|i] = (dp[c][j|i] + ((dp[p][j]*temp)%MOD))%MOD;
        }   
        dp[c][i] = (dp[c][i] + temp)%MOD;
        c=!c;p=!p;
    }           
    cout<<dp[p][511]<<endl;
    return 0;
}

Second solution

#include<bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
using namespace std;

const int mx = 50005;
ll value[mx];
vector<int>adjacent[mx];
vector<int>weak;
bool visited[mx];
int disc[mx];
int low[mx];
int parent[mx];
int tim;

int prime[9] = {2,3,5,7,11,13,17,19,23};
bool ap[mx];

ll POWER(ll a, ll b, ll mod)
{
        ll ret = 1 ;
        while(b)
        {
                if(b & 1 ) ret = ret*a % mod;
                a = a*a % mod;
                b >>= 1 ;
        }
        return ret;
}

void dfs(int u)
{
    visited[u] = true;

    disc[u] = low[u] = ++tim;
    int child = 0;
    for(int i = 0 ; i < adjacent[u].size() ; i++){
        int v = adjacent[u][i];

        if(!visited[v])
        {
            child++;
            parent[v] = u;
            dfs(v);

            low[u] = min(low[u], low[v]);

            if(parent[u] != 0 && low[v] >= disc[u]) ap[u] = true;

            if(parent[u] == 0 && child > 1) ap[u] = true;
        }
        else if(v != parent[u])
        {
            low[u] = min(low[u],disc[v]);
        }
    }
}

int main()
{
    int N , M;
    cin >> N >> M;

    assert(1 <= N <= 50000 && 1 <= M <= 50000);

    for(int i = 1 ; i <= N ; i++) 
        {
            cin>>value[i];
            assert( 1 <= value[i] <= 1000000000);
        }

    for(int i = 1 ; i <= M ; i++)
    {
        int u, v;
        cin >> u >> v;

        assert(1 <= u <= N);
        assert(1 <= v <= N);

        adjacent[u].push_back(v);
        adjacent[v].push_back(u);
    }   

    for(int i = 1 ; i <= N ; i++)
    {
        if(!visited[i]) dfs(i);
    }

    for(int i = 1 ; i <= N ; i++)
    {
        if(ap[i] == true) weak.push_back(i);
    }

    int size = weak.size();

    vector<int>elem;
    ll f[512] = {0};

    for(int i = 0 ; i < size ; i++)
    {
        ll val = value[weak[i]];
        ll ans = 0;
        for(int j = 0 ; j < 9 ; j++)
        {
            int cnt = 0;
            while(val % prime[j] == 0) 
            {
                cnt++;
                val /= prime[j];
            }

            if(cnt > 0)
            {
                ans |= (1 << j);
            } 
        }

        f[ans]++;
        elem.push_back(ans);
    }

    for(int i=0; i<512; i++){
        f[i] = (POWER(2, f[i], MOD)-1+MOD)%MOD;
    }
    
    ll dp[2][10000]={0};
    ll c=1, p=0;
    
    for(int i=0; i<512; i++){
        ll temp=f[i];
        for(int j=0; j<512; j++)
            dp[c][j] = dp[p][j];    
        for(int j=0; j<512; j++){
            dp[c][j|i] = (dp[c][j|i] + ((dp[p][j]*temp)%MOD))%MOD;
        }   
        dp[c][i] = (dp[c][i] + temp)%MOD;
        c=!c;p=!p;
    }   
    
    cout<<dp[p][511]<<endl;
    return 0;

}