Submission #2262112
Source Code Expand
/**
* File : E.cpp
* Author : Kazune Takahashi
* Created : 2018-3-25 21:58:58
* Powered by Visual Studio Code
*/
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define DEBUG 0 // change 0 -> 1 if we need debug.
typedef long long ll;
// const int dx[4] = {1, 0, -1, 0};
// const int dy[4] = {0, 1, 0, -1};
// const int C = 1e6+10;
// const ll M = 1000000007;
const int MAX_SIZE = 1000010;
const long long MOD = 1000000007;
long long inv[MAX_SIZE];
long long fact[MAX_SIZE];
long long factinv[MAX_SIZE];
const int UFSIZE = 100010;
int union_find[UFSIZE];
int root(int a) {
if (a == union_find[a]) return a;
return (union_find[a] = root(union_find[a]));
}
bool issame(int a, int b) {
return root(a) == root(b);
}
void unite(int a, int b) {
union_find[root(a)] = root(b);
}
bool isroot(int a) {
return root(a) == a;
}
void init() {
inv[1] = 1;
for (int i=2; i<MAX_SIZE; i++) {
inv[i] = ((MOD - inv[MOD%i]) * (MOD/i))%MOD;
}
fact[0] = factinv[0] = 1;
for (int i=1; i<MAX_SIZE; i++) {
fact[i] = (i * fact[i-1])%MOD;
factinv[i] = (inv[i] * factinv[i-1])%MOD;
}
for (auto i=0; i<UFSIZE; i++) {
union_find[i] = i;
}
}
long long C(int n, int k) {
if (n >=0 && k >= 0 && n-k >= 0) {
return ((fact[n] * factinv[k])%MOD * factinv[n-k])%MOD;
}
return 0;
}
long long power(long long x, long long n) {
if (n == 0) {
return 1;
} else if (n%2 == 1) {
return (x * power(x, n-1)) % MOD;
} else {
long long half = power(x, n/2);
return (half * half) % MOD;
}
}
long long gcm(long long a, long long b) {
if (a < b) {
return gcm(b, a);
}
if (b == 0) return a;
return gcm(b, a%b);
}
typedef tuple<ll, int, int> edge;
typedef tuple<ll, int> path;
int N, M;
ll X;
vector<edge> V;
vector<path> T[1010];
vector<edge> W;
path parent[10][1010];
int depth[1010];
void dfs(int v, int p, ll cost, int d)
{
parent[0][v] = path(cost, p);
depth[v] = d;
for (auto x : T[v])
{
if (get<1>(x) != p)
{
dfs(get<1>(x), v, get<0>(x), d + 1);
}
}
}
void init2()
{
dfs(0, -1, 0, 0);
for (auto k = 0; k+1 < 10; k++)
{
for (auto v = 0; v < N; v++)
{
if (get<1>(parent[k][v]) < 0)
{
parent[k + 1][v] = path(0, -1);
}
else
{
ll cost = get<0>(parent[k][v]);
int u = get<1>(parent[k][v]);
int new_u = get<1>(parent[k][u]);
ll new_cost = max(cost, get<0>(parent[k][u]));
parent[k + 1][v] = path(new_cost, new_u);
#if DEBUG == 1
cerr << "parent[" << k + 1 << "][" << v << "] = (" << new_cost << ", " << new_u << ")" << endl;
#endif
}
}
}
}
ll lca(int u, int v)
{
if (depth[u] > depth[v])
swap(u, v);
ll ans = 0;
#if DEBUG == 1
cerr << "depth[" << u << "] = " << depth[u]
<< ", depth[" << v << "] = " << depth[v] << endl;
#endif
for (auto k = 0; k < 10; k++)
{
if ((depth[v] - depth[u]) >> k & 1)
{
ans = max(ans, get<0>(parent[k][v]));
v = get<1>(parent[k][v]);
}
}
if (u == v)
return ans;
for (auto k = 9; k >= 0; k--)
{
if (get<1>(parent[k][u]) != get<1>(parent[k][v]))
{
u = get<1>(parent[k][u]);
v = get<1>(parent[k][v]);
ans = max(ans, get<0>(parent[k][u]));
ans = max(ans, get<0>(parent[k][v]));
}
}
ans = max(ans, get<0>(parent[0][v]));
ans = max(ans, get<0>(parent[0][u]));
return ans;
}
int main()
{
init();
cin >> N >> M;
cin >> X;
for (auto i = 0; i < M; i++)
{
int u, v;
ll w;
cin >> u >> v >> w;
u--;
v--;
V.push_back(edge(w, u, v));
}
sort(V.begin(), V.end());
ll Y = 0;
for (auto e : V)
{
ll cost = get<0>(e);
int u = get<1>(e);
int v = get<2>(e);
if (!issame(u, v))
{
unite(u, v);
T[u].push_back(path(cost, v));
T[v].push_back(path(cost, u));
Y += cost;
}
else
{
W.push_back(e);
}
}
#if DEBUG == 1
cerr << "X = " << X << ", Y = " << Y << endl;
#endif
if (X < Y)
{
cout << 0 << endl;
return 0;
}
ll ans = 0;
ll K = N - 1;
ll L = W.size();
if (X == Y)
{
ans = (((power(2, K) + MOD - 2) % MOD) * power(2, L)) % MOD;
}
#if DEBUG == 1
cerr << "L = " << L << ", ans = " << ans << endl;
#endif
init2();
ll L1 = 0;
ll L2 = 0;
for (auto e : W)
{
ll cost = get<0>(e);
int u = get<1>(e);
int v = get<2>(e);
ll temp = cost - lca(u, v);
if (temp < X - Y)
L2++;
else if (temp == X - Y)
L1++;
}
#if DEBUG == 1
cerr << "L1 = " << L1 << ", L2 = " << L2 << endl;
#endif
ans += (2 * (power(2, L - L2) + MOD - power(2, L - L2 - L1))) % MOD;
ans %= MOD;
cout << ans << endl;
}
Submission Info
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 900 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt |
All |
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 |
WA |
40 ms |
24320 KB |
02.txt |
WA |
40 ms |
24320 KB |
03.txt |
AC |
40 ms |
24320 KB |
04.txt |
WA |
40 ms |
24448 KB |
05.txt |
WA |
40 ms |
24448 KB |
06.txt |
WA |
40 ms |
24320 KB |
07.txt |
WA |
40 ms |
24448 KB |
08.txt |
AC |
40 ms |
24320 KB |
09.txt |
WA |
40 ms |
24448 KB |
10.txt |
AC |
40 ms |
24448 KB |
11.txt |
AC |
40 ms |
24320 KB |
12.txt |
AC |
39 ms |
24320 KB |
13.txt |
AC |
39 ms |
24320 KB |
14.txt |
AC |
39 ms |
24320 KB |
15.txt |
WA |
40 ms |
24320 KB |
16.txt |
AC |
40 ms |
24320 KB |
17.txt |
WA |
40 ms |
24320 KB |
18.txt |
AC |
41 ms |
24192 KB |
19.txt |
WA |
40 ms |
24448 KB |
20.txt |
AC |
40 ms |
24192 KB |
21.txt |
WA |
41 ms |
24320 KB |
22.txt |
AC |
41 ms |
24448 KB |
23.txt |
AC |
41 ms |
24448 KB |
24.txt |
WA |
40 ms |
24320 KB |
25.txt |
AC |
39 ms |
24320 KB |
26.txt |
WA |
40 ms |
24320 KB |
27.txt |
WA |
40 ms |
24320 KB |
28.txt |
WA |
45 ms |
24320 KB |
29.txt |
WA |
41 ms |
24448 KB |
30.txt |
WA |
40 ms |
24320 KB |
31.txt |
AC |
41 ms |
24448 KB |
32.txt |
WA |
40 ms |
24320 KB |
33.txt |
WA |
41 ms |
24320 KB |
34.txt |
AC |
40 ms |
24320 KB |
35.txt |
WA |
40 ms |
24320 KB |
36.txt |
WA |
40 ms |
24320 KB |
37.txt |
WA |
40 ms |
24320 KB |
38.txt |
AC |
40 ms |
24320 KB |
39.txt |
AC |
40 ms |
24320 KB |
40.txt |
AC |
40 ms |
24448 KB |
41.txt |
AC |
40 ms |
24320 KB |
42.txt |
AC |
39 ms |
24320 KB |
43.txt |
AC |
39 ms |
24320 KB |
44.txt |
AC |
40 ms |
24192 KB |
45.txt |
WA |
40 ms |
24320 KB |
46.txt |
WA |
40 ms |
24320 KB |
47.txt |
AC |
39 ms |
24320 KB |
48.txt |
AC |
39 ms |
24320 KB |
sample-01.txt |
AC |
38 ms |
24192 KB |
sample-02.txt |
AC |
38 ms |
24192 KB |
sample-03.txt |
AC |
38 ms |
24064 KB |
sample-04.txt |
AC |
38 ms |
24192 KB |