Submission #5035957

---

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;
}

ll dfs(int now, int past, int dst, ll ma, VVL &e, VVL &c){
    if (now == dst) return ma;
    ll ret = 0;
    REP(i,e[now].size()){
        int next = e[now][i];
        if (next == past) continue;
        ret = max(ret, dfs(next, now, dst, max(ma, c[now][i]), e, c));
    }
    return ret;
}

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;
    }

    ll s = 0, p = 0, ma = 0;
    union_find uf;
    uf.init(n);
    VVL e(n), c(n);
    REP(i,m){
        int j = i;
        while (j < m && w[j] == w[i]) j++;
        ll pp = p;
        // cout << i << " " << j << endl;
        FOR(k,i,j-1){
            if (!uf.same(u[k], v[k])) p++;
        }
        set<int> st;
        FOR(k,i,j-1){
            if (!uf.same(u[k], v[k])){
                uf.merge(u[k], v[k]);
                s += w[k];
                pp++;
                st.insert(k);
            }
        }
        if (pp == n - 1){
            ma = w[i];
            break;
        }
        for (int k : st){
            e[u[k]].push_back(v[k]);
            c[u[k]].push_back(w[k]);
            e[v[k]].push_back(u[k]);
            c[v[k]].push_back(w[k]);
        }
        p = pp;
        i = j - 1;
    }

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

    if (s == x){
        ll c = 0;
        REP(i,m){
            union_find uf;
            uf.init(n);
            uf.merge(u[i], v[i]);
            ll s = w[i];
            REP(j,m){
                if (!uf.same(u[j], v[j])){
                    s += w[j];
                    uf.merge(u[j], v[j]);
                }
            }
            if (s == x) c++;
        }
        ll ans = (powll(2, c) - 2 + mod) % mod;
        ans = (ans * powll(m - c, 2)) % mod;
        cout << ans << endl;
        return 0;
    }

    uf.init(n);
    REP(i,n){
        for (int j : e[i]) uf.merge(i, j);
    }

    VL d(m);
    REP(i,m){
        if (!uf.same(u[i], v[i])){
            d[i] = w[i] - ma;
        }else{
            d[i] = w[i] - dfs(u[i], -1, v[i], 0, e, c);
        }
    }

    ll c1 = 0, c2 = 0;
    REP(i,m){
        if (d[i] == x - s) c1++;
        if (d[i] > x - s) c2++;
    }
    ll ans = ((powll(2, c1) - 1) * powll(2, c2)) % mod;
    ans = (2 * ans) % mod;
    cout << ans << endl;

    return 0;
}

Submission Info

Compile Error

./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