HackerEarth Final battle problem solution

In this HackerEarth Final battle problem solution Monique and Paul both enjoy math and programming a lot. A few days ago they decided to compete against each other in many kinds of problem solving competitions. They solved hundreds of problems, but they still have not decided who the winner is, because the current score is surprisingly a draw. Monique gets impatient, and proposed a final game to decide the battle between them. The game is played as follows:

First, Monique constructs a tree with N nodes and binary weights on the edges of the tree. The weights are not known initially, but the structure of the tree is. After that, she writes down a list of Q distinct queries of the form:

 query(v,u) - returns a parity of the sum of values on edges on the path from node v to node u in the tree. Each query has assigned a cost  denoting the cost c(v,u) of asking that query.

Finally, she gives Paul two days to find the number of subsets S of the set of all queries such that after asking all queries from S, Paul can be sure what values are assigned to all edges of the tree Monique constructed and that the sum of costs of queries in S is the lowest from all such subsets. Since this number can be very large, Paul has to return it modulo 10^9 + 7.

The task is to help Paul solve the problem, so he can defeat Monique.

HackerEarth Final battle problem solution.

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define ALL(t) t.begin(),t.end()
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));

typedef long long ll;
typedef vector<ll> Vec;
typedef vector<Vec> Matrix;

const int MOD = 1e9 + 7;
const int MINN = 2;
const int MAXN = 75;
const int MINM = 1;
const int MAXM = MAXN * (MAXN - 1) / 2;
const int MINW = 1;
const int MAXW = 1e5;

bool in_range(int v, int a, int b)
{
    return v >= a && v <= b;
}

inline ll modulo(ll a, ll b) {
      const ll result = a % b;
        return result >= 0 ? result : result + b;
}

ll mypow(ll a, ll b)
{
    if(b == 0) return 1;
    if(b % 2 == 0)
    {
        ll c = mypow(a, b / 2);
        return modulo(c * c, MOD);
    }
    return modulo(a * mypow(a, b - 1), MOD);
}

ll mod_rev(ll a)
{
    return mypow(a, MOD - 2);
}

ll div_mod(ll a, ll b)
{
    return modulo(a * mod_rev(b), MOD);
}

void print_matrix(Matrix& m, int n)
{
    FOR(i, n)
    {
        FOR(j, n) 
        {
            if(m[i][j] >= 0) cout << " ";
            cout << m[i][j] << " ";
        }
        cout << endl;
    }
}

Matrix empty_matrix(int n)
{
    Matrix m(n, Vec(n, 0));
    return m;
}

Vec multiply(const Vec& v, int n, ll c)
{
    Vec res(n);
    FOR(i, n) 
    {
        res[i] = modulo(v[i] * c, MOD);
    }
    return res;
}

Vec subtract(const Vec& a, const Vec& b, int n)
{
    assert(n <= a.size());
    assert(n <= b.size());
    Vec res(n);
    FOR(i, n)
    {
        res[i] = modulo(a[i] - b[i], MOD);
    }
    return res;
}

ll submatrix_determinant_by_gauss(Matrix& a, int n)
{
    assert(n <= a.size());
    assert(n <= a[0].size());
    ll det = 1;
    FOR(i, n)
    {
        int maxpivot = a[i][i];
        int maxpivot_index = i;
        REP(k, i + 1, n - 1) 
        {
            if(a[k][i] > maxpivot)
            {
                maxpivot = a[k][i];
                maxpivot_index = k;
            }
        }
        if(maxpivot % MOD == 0)
        {
            //a is singular
            return 0;
        }
        if(maxpivot_index != i)
        {
            swap(a[maxpivot_index], a[i]);
            det = modulo(det * -1, MOD);
        }
        REP(k, i + 1, n - 1)
        {
            ll c = div_mod(a[k][i], a[i][i]);
            Vec tmp = multiply(a[i], n, c);
            a[k] = subtract(a[k], tmp, n);
        }
    }
    FOR(i, n)
    {
        det = modulo(det * a[i][i], MOD);
    }
    return det;
}



//Union find
int uf_member[MAXN];
int uf_rank[MAXN];

int uf_find(int v)
{
    if(uf_member[v] == v) return v;
    int fv = uf_find(uf_member[v]);
    uf_member[v] = fv;
    return fv;
}

bool uf_union(int v, int u)
{
    int fv = uf_find(v);
    int fu = uf_find(u);
    
    if(fv == fu) return false;
    if(uf_rank[fv] < uf_rank[fu])
    {
        uf_member[fv] = fu;
        uf_rank[fu] += uf_rank[fv];
    }
    else
    {
        uf_member[fu] = fv;
        uf_rank[fv] += uf_rank[fu];
    }
    return true;
}

void init_uf(int n)
{
    FOR(i, n) uf_member[i] = i;
    FOR(i, n) uf_rank[i] = 1;
}

vector<pii> apply_find_to_edges(const vector<pii> edges)
{
    vector<pii> res;
    FOR(i, edges.size())
    {
        pii e = edges[i];
        res.pb(mp(uf_find(e.fi), uf_find(e.se)));
    }
    return res;
}

ll res = 1;

vi g[MAXN];
bool visited[MAXN];

map<int, int> component_vertices;
vector<pii> component_edges;

void dfs(int v)
{
    visited[v] = 1;
    if(component_vertices.find(v) == component_vertices.end())
    {
        component_vertices.insert(mp(v, SZ(component_vertices)));
    }
    int mv = component_vertices[v];
    FOR(i, SZ(g[v]))
    {
        int u = g[v][i];
        if(component_vertices.find(u) == component_vertices.end())
        {
            component_vertices.insert(mp(u, SZ(component_vertices)));
        }
        int mu = component_vertices[u];
        component_edges.pb(mp(mv, mu));
        if(!visited[u])
        {
            dfs(u);
        }
    }
}

void solve(vector<pii> edges)
{
    set<int> vertices;
    FOR(i, edges.size())
    {
        int v = edges[i].fi;
        int u = edges[i].se;
        g[v].pb(u);
        g[u].pb(v);
        vertices.insert(v);
        vertices.insert(u);
    }

    for(auto it = vertices.begin(); it != vertices.end(); ++it)
    {
        int v = *it;
        if(!visited[v])
        {
            component_edges.clear();
            component_vertices.clear();

            dfs(v);

            int n = SZ(component_vertices);
            Matrix m = empty_matrix(n);
            FOR(i, component_edges.size())
            {
                int v = component_edges[i].fi;
                int u = component_edges[i].se;
                if(v == u) continue;
                m[v][v]++;
                m[v][u]--;
            }

            ll subres = submatrix_determinant_by_gauss(m, n - 1);
            res *= subres;
            res %= MOD;
        }
    }
    
    //clear up
    for(auto it = vertices.begin(); it != vertices.end(); ++it)
    {
        int v = *it;
        g[v].clear();
        visited[v] = 0;
    }
}

int dfs_cnt(int v)
{
    visited[v] = 1;
    int res = 1;
    FOR(i, g[v].size())
    {
        int u = g[v][i];
        if(!visited[u])
        {
            res += dfs_cnt(u);
        }
    }
    return res;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    FOR(i, n - 1)
    {
        int dummy_v, dummy_u;
        scanf("%d %d", &dummy_v, &dummy_u);
    }

    assert(in_range(n, MINN, MAXN));
    assert(in_range(m, MINM, MAXM));


    set<pii> distinct_edges;
    map<int, vector<pii>> edges;
    FOR(i, m)
    {
        int v, u, w;
        scanf("%d %d %d", &v, &u, &w);
        assert(in_range(v, 1, n));
        assert(in_range(u, 1, n));
        assert(in_range(w, MINW, MAXW));
        --v; --u;
        if(u < v) swap(v, u);
        distinct_edges.insert(mp(v, u));
        if(edges.find(w) == edges.end())
        {
            edges[w] = vector<pii>();
        }
        edges[w].pb(mp(v, u));
        g[v].pb(u);
        g[u].pb(v);
    }
    assert(distinct_edges.size() == m);

    //check if g is connected
    int cnt = dfs_cnt(0); 
    if(cnt < n) 
    {
        printf("0\n");
        return 0;
    }
    FOR(i, n) visited[i] = 0;
    FOR(i, n) g[i].clear();


    init_uf(n);

    for(auto it = edges.begin(); it != edges.end(); ++it)
    {
        vector<pii> tmp_edges = apply_find_to_edges(it->se);
        solve(tmp_edges);

        FOR(i, SZ(tmp_edges))
        {
            int v = tmp_edges[i].fi;
            int u = tmp_edges[i].se;
            uf_union(v, u);
        }
    }

    printf("%d\n", (int)res);

    return 0;
}

Second solution

#include<bits/stdc++.h>

#define bs 1000000007

using namespace std;

const int N = 105000;

int n, Q;
int w[N];
int a[N], b[N], c[N];
vector<int> by_weight[N];
int cur_comps;
int mapp[N];

int get(int x)
{
    if (x == w[x])
    {
        return x;
    }
    return w[x] = get(w[x]);
}

void merge(int a, int b)
{
    a = get(a);
    b = get(b);
    if (a == b)
        return;
    --cur_comps;
    w[a] = b;
}

vector<vector<long long> > normalize(vector<vector<long long> > v)
{
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = 0; j < v[i].size(); j++)
        {
            v[i][j] %= bs;
            if (v[i][j] < 0)
                v[i][j] += bs;
        }
    }
    return v;
}

int mult(int a, int b)
{
    long long res = 1ll * a*b;
    res %= bs;
    if (res < 0)
        res += bs;
    return res;
}

long long pw(long long a, long long b)
{
    if (b == 0)
        return 1;
    if (b % 2)
        return a*pw(a, b - 1) % bs;
    return pw(a*a%bs, b / 2);
}

int inv(long long x)
{
    return pw(x, bs - 2);
}

int sub(int a, int b)
{
    a -= b;
    a %= bs;
    if (a < 0)
        a += bs;
    return a;
}

long long get_det(vector<vector<long long> > v)
{
    long long res = 1;
    int n = v.size();

    int det = 1;

    for (int i = 0; i < n; i++)
    {
        int k = i;
        for (int j = i + 1; j < n; j++)
        {
            if (v[j][i]>v[k][i])
                k = j;
        }

        if (v[k][i] == 0)
        {
            return 0;
        }

        swap(v[i], v[k]);

        if (i != k)
        {
            det = mult(det, -1);
        }
        det = mult(det, v[i][i]);

        for (int j = i + 1; j < n; j++)
        {
            v[i][j] = mult(v[i][j], inv(v[i][i]));
        }

        for (int j = 0; j < n; j++)
        {
            if (j != i&&v[j][i]>0)
            {
                for (int k = i + 1; k < n; k++)
                {
                    v[j][k] = sub(v[j][k], mult(v[i][k], v[j][i]));
                }
            }
        }
    }
    return det;
}

int used[N];
vector<int> G[N];
int taken[N];
vector<int> visited;

void dfs(int v)
{
    used[v] = 1;
    visited.push_back(v);
    for (int i = 0; i < G[v].size(); i++)
    {
        int to = G[v][i];
        if (used[to])
            continue;
        dfs(to);
    }
}

vector<vector<long long> > update(vector<vector<long long> > v)
{
    v.erase(v.begin());
    for (int i = 0; i < v.size(); i++)
    {
        v[i].erase(v[i].begin());
    }
    return v;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> Q;
    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
    }

    for (int i = 1; i <= Q; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        --a[i];
        --b[i];
        by_weight[c[i]].push_back(i);
    }

    for (int i = 0; i <= n; i++)
    {
        w[i] = i;
    }

    cur_comps = n;

    long long ans = 1;

    for (int i = 1; i <= 100000; i++)
    {
        if (by_weight[i].size() == 0)
            continue;

        for (int j = 0; j < n; j++)
        {
            used[j] = 0;
            G[j].clear();
        }

        for (int j = 0; j < by_weight[i].size(); j++)
        {
            int id = by_weight[i][j];
            G[get(a[id])].push_back(get(b[id]));
            G[get(b[id])].push_back(get(a[id]));
        }

        for (int j = 0; j < n; j++)
        {
            if (used[j])
                continue;
            if (G[j].size() == 0)
                continue;
            visited.clear();
            dfs(j);
            for (int q = 0; q < n; q++)
            {
                taken[q] = 0;
            }

            int cnt = 0;
            vector<int> v2;
            for (int q = 0; q < visited.size(); q++)
            {
                v2.push_back(get(visited[q]));
            }
            sort(v2.begin(), v2.end());

            for (int q = 0; q < v2.size(); q++)
            {
                if (q == 0 || v2[q] != v2[q - 1])
                {

                    taken[v2[q]] = cnt;
                    ++cnt;
                }
            }

            vector<vector<long long> > V;
            V.resize(cnt);
            for (int i = 0; i < V.size(); i++)
            {
                V[i].resize(cnt);
                for (int j = 0; j < V[i].size(); j++)
                {
                    V[i][j] = 0;
                }
            }

            for (int j = 0; j < visited.size(); j++)
            {
                int v = visited[j];
                int id1 = get(v);
                for (int q = 0; q < G[v].size(); q++)
                {
                    int to = G[v][q];
                    int id2 = get(to);
                    id1 = taken[get(v)];
                    id2 = taken[id2];
                    V[id1][id2]--;
                    V[id1][id1]++;
                }
            }
            V = normalize(V);
            V = update(V);
            ans = mult(ans, get_det(V));
        }

        for (int j = 0; j < by_weight[i].size(); j++)
        {
            int id = by_weight[i][j];
            int id1 = a[id];
            int id2 = b[id];
            id1 = get(id1);
            id2 = get(id2);
            merge(id1, id2);
        }

    }

    if (cur_comps > 1)
    {
        cout << 0 << endl;
    }
    else
    {
        cout << ans << endl;
    }

    cin.get(); cin.get();
    return 0;
}