Submission #5032160

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;
typedef vector<VD> VVD;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

struct union_find{
    VI par, sz;

    void init(int n){
        par.resize(n);
        sz.assign(n, 1);
        REP(i,n) par[i] = i;
    }

    int find(int x){
        if (par[x] == x) return x;
        else return par[x] = find(par[x]);
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }

    void merge(int x, int y){
        x = find(x);
        y = find(y);
        if (x == y) return;
        par[x] = y;
        sz[y] += sz[x];
    }

    int size(int x){
        return sz[find(x)];
    }
};


const ll mod = 1000000007;

ll add(ll x, ll y){
    return (x+y)%mod;
}

ll mul(ll x, ll y){
    return (x%mod)*(y%mod)%mod;
}

ll powll(ll x, ll y){
    ll res = 1LL;
    while(y){
        if (y & 1LL)
            res *= x;
        res %= mod;
        x = (x*x) % mod;
        y >>= 1LL;
    }
    return res;
}

int main() {
    ll n, m, x;
    cin >> n >> m >> x;
    vector<pair<ll, P>> tmp(m);
    REP(i,m){
        ll u = in() - 1, v = in() - 1, w = in();
        tmp[i] = make_pair(w, P(u, v));
    }
    sort(ALL(tmp));
    VI u(m), v(m);
    VL w(m);
    REP(i,m){
        u[i] = tmp[i].second.first;
        v[i] = tmp[i].second.second;
        w[i] = tmp[i].first;
    }

    VI used(m);
    ll s = 0, p = 0;
    union_find uf;
    uf.init(n);
    REP(i,m){
        int j = i;
        while (j < m && w[j] == w[i]) j++;
        ll pp = p;
        FOR(k,i,j-1){
            if (!uf.same(u[k], v[k])) p++;
        }
        FOR(k,i,j-1){
            if (!uf.same(u[k], v[k])){
                uf.merge(u[k], v[k]);
                s += w[k];
                pp++;
            }
        }
        if (pp == n - 1){
            break;
        }
        p = pp;
        i = j - 1;
    }

    if (s > x){
        cout << 0 << endl;
        return 0;
    }

    if (s == x){
        ll ans = (powll(2, p) - 2) * powll(2, m - p);
        ans = ((ans % mod) + mod) % mod;
        cout << ans << endl;
        return 0;
    }

    cout << 1 / 0 << endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:145:15: warning: division by zero [-Wdiv-by-zero]
     cout << 1 / 0 << endl;
               ^
./Main.cpp: In function ‘int in()’:
./Main.cpp:34:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int in() { int x; scanf("%d", &x); return x; }
                                  ^
./Main.cpp: In function ‘ll lin()’:
./Main.cpp:35:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll lin() { ll x; scanf("%lld", &x); return x; }
                                   ^

Judge Result