Submission #2281768


Source Code Expand

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll,P> LP;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

struct UnionFind{
  vector<int> v;
  UnionFind(int n) : v(n, -1) {}
  void init(){ for(int i = 0;i < v.size();i++)v[i]=-1; }
  int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (-v[x] < -v[y]) swap(x, y);
    v[x] += v[y]; v[y] = x;
    return true;
  }
  bool root(int x) { return v[x] < 0; }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -v[find(x)]; }
};


ll n,m;
ll x;
vector<LP> es;

ll mod_pow(ll a,ll n){
  ll res=1;
  while(n>0){
    if(n&1)res=res*a%mod;
    a=a*a%mod;
    n=n>>1;
  }
  return res;
}

int main(){
  cin>>n>>m;
  cin>>x;
  rep(i,m){
    ll a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    es.push_back(LP(c,P(a,b)));
  }
  sort(all(es));
  ll res=0;
  rep(i,m){
    UnionFind uf(n);
    uf.unite(es[i].se.fi,es[i].se.se);
    ll sum=es[i].fi;
    rep(j,m){
      if(i==j)continue;
      if(uf.same(es[j].se.fi,es[j].se.se))continue;
      sum+=es[j].fi;
      uf.unite(es[j].se.fi,es[j].se.se);
    }
    if(uf.size(0)!=n||sum!=x)continue;
    res=(res+mod_pow(2,m-1-i))%mod;
  }
  cout<<res*2%mod<<endl;
  return 0;
}

Submission Info

Submission Time
Task E - Bichrome Spanning Tree
User yamad
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1890 Byte
Status
Exec Time 44 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 36 ms 384 KB
02.txt 36 ms 384 KB
03.txt 37 ms 384 KB
04.txt 39 ms 384 KB
05.txt 38 ms 384 KB
06.txt 36 ms 384 KB
07.txt 39 ms 384 KB
08.txt 37 ms 384 KB
09.txt 42 ms 384 KB
10.txt 39 ms 384 KB
11.txt 33 ms 384 KB
12.txt 12 ms 256 KB
13.txt 12 ms 256 KB
14.txt 12 ms 256 KB
15.txt 38 ms 384 KB
16.txt 35 ms 384 KB
17.txt 37 ms 384 KB
18.txt 37 ms 384 KB
19.txt 37 ms 384 KB
20.txt 39 ms 384 KB
21.txt 41 ms 384 KB
22.txt 40 ms 384 KB
23.txt 38 ms 384 KB
24.txt 11 ms 256 KB
25.txt 12 ms 256 KB
26.txt 33 ms 384 KB
27.txt 37 ms 384 KB
28.txt 41 ms 384 KB
29.txt 40 ms 384 KB
30.txt 42 ms 384 KB
31.txt 39 ms 384 KB
32.txt 36 ms 384 KB
33.txt 35 ms 384 KB
34.txt 29 ms 384 KB
35.txt 22 ms 384 KB
36.txt 22 ms 384 KB
37.txt 21 ms 384 KB
38.txt 37 ms 384 KB
39.txt 44 ms 384 KB
40.txt 39 ms 384 KB
41.txt 34 ms 384 KB
42.txt 15 ms 384 KB
43.txt 12 ms 256 KB
44.txt 11 ms 256 KB
45.txt 15 ms 384 KB
46.txt 22 ms 384 KB
47.txt 12 ms 256 KB
48.txt 15 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