Submission #2642385

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
    cerr << a << ", X=" << X << endl;
    fprintf(stderr, "num<x-1>=%d, num<x>=%d, (M=%d, N=%d)\n", num_x_1, num_x, M, N);
    fprintf(stderr, "f(X-1) = f(%lld) = %lld, f(X) = f(%lld) = %lld\n",
            num_x_1, f(num_x_1), num_x, f(num_x));
#endif
    // return f(num_x_1) - f(num_x);
    return SUB(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 900
Code Size 3802 Byte
Status
Exec Time 429 ms
Memory 512 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 900 / 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 275 ms 384 KB
02.txt 305 ms 384 KB
03.txt 271 ms 384 KB
04.txt 275 ms 384 KB
05.txt 273 ms 384 KB
06.txt 277 ms 384 KB
07.txt 277 ms 384 KB
08.txt 345 ms 384 KB
09.txt 429 ms 384 KB
10.txt 274 ms 512 KB
11.txt 291 ms 384 KB
12.txt 105 ms 256 KB
13.txt 105 ms 256 KB
14.txt 105 ms 256 KB
15.txt 359 ms 384 KB
16.txt 270 ms 384 KB
17.txt 298 ms 384 KB
18.txt 275 ms 384 KB
19.txt 282 ms 384 KB
20.txt 272 ms 384 KB
21.txt 364 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 291 ms 384 KB
27.txt 286 ms 384 KB
28.txt 299 ms 384 KB
29.txt 310 ms 384 KB
30.txt 347 ms 384 KB
31.txt 312 ms 384 KB
32.txt 327 ms 384 KB
33.txt 330 ms 384 KB
34.txt 329 ms 384 KB
35.txt 100 ms 384 KB
36.txt 99 ms 384 KB
37.txt 105 ms 384 KB
38.txt 308 ms 384 KB
39.txt 285 ms 384 KB
40.txt 289 ms 384 KB
41.txt 307 ms 384 KB
42.txt 171 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 107 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