Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #2261434

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 x,ll n){
ll res=1;
while(n>0){
if(n&1)res=res*x%mod;
x=x*x%mod;
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;
for(ll i=m-1;i>=1;i--){
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 2018-03-25 22:37:37+0900 E - Bichrome Spanning Tree yamad C++14 (GCC 5.4.1) 0 1921 Byte WA 41 ms 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 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 37 ms 384 KB
02.txt 35 ms 384 KB
03.txt 36 ms 384 KB
04.txt 39 ms 384 KB
05.txt 38 ms 384 KB
06.txt 36 ms 384 KB
07.txt 38 ms 384 KB
08.txt 35 ms 384 KB
09.txt 41 ms 384 KB
10.txt 38 ms 384 KB
11.txt 36 ms 384 KB
12.txt 12 ms 256 KB
13.txt 12 ms 256 KB
14.txt 12 ms 256 KB
15.txt 39 ms 384 KB
16.txt 36 ms 384 KB
17.txt 37 ms 384 KB
18.txt 36 ms 384 KB
19.txt 38 ms 384 KB
20.txt 39 ms 384 KB
21.txt 40 ms 384 KB
22.txt 38 ms 384 KB
23.txt 38 ms 384 KB
24.txt 12 ms 256 KB
25.txt 12 ms 256 KB
26.txt 36 ms 384 KB
27.txt 37 ms 384 KB
28.txt 41 ms 384 KB
29.txt 40 ms 384 KB
30.txt 40 ms 384 KB
31.txt 39 ms 384 KB
32.txt 36 ms 384 KB
33.txt 35 ms 384 KB
34.txt 30 ms 384 KB
35.txt 22 ms 384 KB
36.txt 22 ms 384 KB
37.txt 21 ms 384 KB
38.txt 36 ms 384 KB
39.txt 39 ms 384 KB
40.txt 38 ms 512 KB
41.txt 38 ms 384 KB
42.txt 15 ms 384 KB
43.txt 12 ms 384 KB
44.txt 11 ms 256 KB
45.txt 16 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