Submission #2642188

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

const ll MOD=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % MOD; }
ll SUB(ll x, ll y) { return (x-y+MOD) % MOD; }
ll MUL(ll x, ll y) { return x*y % MOD; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { /*assert(y%MOD!=0);*/ return MUL(x, POW(y, MOD-2)); }
// ll comb(ll n, ll k) { ll v=1; for(ll i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }

class UnionFind {
  vector<int> data;
 public:
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};

int N, M;
ll X;
vector<int> u, v, w;

ll mst_cost(int start_edge){
    UnionFind uf(N);
    uf.unionSet(u[start_edge], v[start_edge]);
    ll total_weight = w[start_edge];
    priority_queue<pair<int,ii>> pq;
    rep(e,M) {
        if (e == start_edge) continue;
        pq.push(make_pair(-w[e], ii(u[e], v[e])));
    }
    int conn_count = 1;
    while (!pq.empty() && conn_count < N-1) {
        auto p = pq.top(); pq.pop();
        int weight = -p.first;
        int ue = p.second.first, ve = p.second.second;
        if (uf.findSet(ue,ve)) continue;
        uf.unionSet(ue,ve);
        total_weight += weight;
        ++conn_count;
    }
    return total_weight;
}

ll f(int num) {
    if (num == 0)
        return POW(2, M);
    else
        return POW(2, M-num+1);
}

ll solve() {
    rep(e,M) { --u[e]; --v[e]; } // [1..M] -> [0..M-1]

    vector<ll> a(M);
    rep(e,M) a[e] = mst_cost(e);
    sort(ALL(a));
    auto rng = equal_range(ALL(a), X);
    if (rng.first == rng.second) return 0LL;

    int num_x_1 = rng.first - a.begin();
    int num_x = rng.second - a.begin();
#ifdef DEBUG
    fprintf(stderr, "num<x-1>=%d, num<x>=%d, (M=%d, N=%d)\n", num_x_1, num_x, M, N);
#endif
    return f(num_x_1) - f(num_x);
}

int main() {
    cin >>N>>M; // 1−1000,1-2000
    cin >>X; // 1-1e12
    // vector<int> u(M),v(M),w(M); //u,v:1-N, w:1-1e9
    u.resize(M); v.resize(M); w.resize(M);
    rep(i,M){
        cin >> u[i] >> v[i] >> w[i];
    }
    cout << solve() << endl;
    return 0;
}

Submission Info

Submission Time
Task E - Bichrome Spanning Tree
User naoya_t
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3596 Byte
Status
Exec Time 427 ms
Memory 384 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
All 0 / 900 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Case Name Status Exec Time Memory
01.txt 274 ms 384 KB
02.txt 304 ms 384 KB
03.txt 270 ms 384 KB
04.txt 275 ms 384 KB
05.txt 273 ms 384 KB
06.txt 276 ms 384 KB
07.txt 276 ms 384 KB
08.txt 344 ms 384 KB
09.txt 427 ms 384 KB
10.txt 273 ms 384 KB
11.txt 288 ms 384 KB
12.txt 105 ms 256 KB
13.txt 104 ms 256 KB
14.txt 105 ms 256 KB
15.txt 358 ms 384 KB
16.txt 269 ms 384 KB
17.txt 297 ms 384 KB
18.txt 275 ms 384 KB
19.txt 281 ms 384 KB
20.txt 271 ms 384 KB
21.txt 363 ms 384 KB
22.txt 273 ms 384 KB
23.txt 275 ms 384 KB
24.txt 105 ms 256 KB
25.txt 105 ms 256 KB
26.txt 290 ms 384 KB
27.txt 285 ms 384 KB
28.txt 297 ms 384 KB
29.txt 309 ms 384 KB
30.txt 344 ms 384 KB
31.txt 312 ms 384 KB
32.txt 327 ms 384 KB
33.txt 330 ms 384 KB
34.txt 328 ms 384 KB
35.txt 99 ms 384 KB
36.txt 99 ms 384 KB
37.txt 106 ms 384 KB
38.txt 304 ms 384 KB
39.txt 284 ms 384 KB
40.txt 289 ms 384 KB
41.txt 306 ms 384 KB
42.txt 170 ms 256 KB
43.txt 139 ms 256 KB
44.txt 104 ms 256 KB
45.txt 144 ms 256 KB
46.txt 203 ms 384 KB
47.txt 107 ms 256 KB
48.txt 106 ms 256 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB
sample-03.txt 1 ms 256 KB
sample-04.txt 1 ms 256 KB