Submission #2271551
Source Code Expand
/**
* File : E2.cpp
* Author : Kazune Takahashi
* Created : 2018-3-28 12:29:59
* 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;
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() {
for (auto i=0; i<UFSIZE; i++) {
union_find[i] = i;
}
}
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;
}
}
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];
vector<ll> S;
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]))
{
ans = max(ans, get<0>(parent[k][u]));
ans = max(ans, get<0>(parent[k][v]));
u = get<1>(parent[k][u]);
v = get<1>(parent[k][v]);
}
}
ans = max(ans, get<0>(parent[0][v]));
ans = max(ans, get<0>(parent[0][u]));
return ans;
}
ll f(ll n)
{
ll c;
if (S[0] > n)
c = 0;
else
{
ll lb = 0;
ll ub = S.size();
while (ub - lb > 1)
{
ll t = (ub + lb) / 2;
if (S[t] > n)
{
ub = t;
}
else
{
lb = t;
}
}
c = ub;
}
if (c == 0)
{
return power(2, M);
}
else
{
return power(2, M - c + 1);
}
}
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;
int cnt = 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;
cnt++;
}
else
{
W.push_back(e);
}
}
#if DEBUG == 1
cerr << "X = " << X << ", Y = " << Y << endl;
#endif
init2();
for (auto i = 0; i < cnt; i++)
{
S.push_back(Y);
}
for (auto e : W)
{
ll cost = get<0>(e);
int u = get<1>(e);
int v = get<2>(e);
S.push_back(cost - lca(u, v) + Y);
}
sort(S.begin(), S.end());
#if DEBUG == 1
for (auto x : S)
{
cerr << x << " ";
}
cerr << endl;
cerr << "f(" << X - 1 << ") = " << f(X - 1)
<< ", f(" << X << ") = " << f(X) << endl;
#endif
cout << (f(X - 1) + MOD - f(X)) % MOD << endl;
}
Submission Info
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
900 / 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 |
AC |
4 ms |
896 KB |
02.txt |
AC |
4 ms |
896 KB |
03.txt |
AC |
4 ms |
896 KB |
04.txt |
AC |
4 ms |
1024 KB |
05.txt |
AC |
4 ms |
1024 KB |
06.txt |
AC |
4 ms |
896 KB |
07.txt |
AC |
4 ms |
1024 KB |
08.txt |
AC |
4 ms |
896 KB |
09.txt |
AC |
4 ms |
1024 KB |
10.txt |
AC |
4 ms |
1024 KB |
11.txt |
AC |
3 ms |
896 KB |
12.txt |
AC |
3 ms |
896 KB |
13.txt |
AC |
3 ms |
896 KB |
14.txt |
AC |
3 ms |
896 KB |
15.txt |
AC |
4 ms |
896 KB |
16.txt |
AC |
4 ms |
896 KB |
17.txt |
AC |
4 ms |
896 KB |
18.txt |
AC |
4 ms |
1024 KB |
19.txt |
AC |
4 ms |
1024 KB |
20.txt |
AC |
4 ms |
1024 KB |
21.txt |
AC |
4 ms |
1024 KB |
22.txt |
AC |
4 ms |
1024 KB |
23.txt |
AC |
4 ms |
1024 KB |
24.txt |
AC |
3 ms |
896 KB |
25.txt |
AC |
3 ms |
896 KB |
26.txt |
AC |
4 ms |
896 KB |
27.txt |
AC |
4 ms |
896 KB |
28.txt |
AC |
4 ms |
1024 KB |
29.txt |
AC |
4 ms |
1024 KB |
30.txt |
AC |
4 ms |
1024 KB |
31.txt |
AC |
3 ms |
1024 KB |
32.txt |
AC |
3 ms |
1024 KB |
33.txt |
AC |
3 ms |
896 KB |
34.txt |
AC |
3 ms |
896 KB |
35.txt |
AC |
3 ms |
896 KB |
36.txt |
AC |
3 ms |
896 KB |
37.txt |
AC |
3 ms |
896 KB |
38.txt |
AC |
4 ms |
896 KB |
39.txt |
AC |
4 ms |
1024 KB |
40.txt |
AC |
4 ms |
1024 KB |
41.txt |
AC |
4 ms |
896 KB |
42.txt |
AC |
3 ms |
896 KB |
43.txt |
AC |
2 ms |
896 KB |
44.txt |
AC |
3 ms |
896 KB |
45.txt |
AC |
3 ms |
896 KB |
46.txt |
AC |
3 ms |
1024 KB |
47.txt |
AC |
2 ms |
896 KB |
48.txt |
AC |
2 ms |
896 KB |
sample-01.txt |
AC |
1 ms |
768 KB |
sample-02.txt |
AC |
1 ms |
640 KB |
sample-03.txt |
AC |
1 ms |
640 KB |
sample-04.txt |
AC |
1 ms |
768 KB |