Submission #5032664
Source Code Expand
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
using namespace std;
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
typedef vector<double> VD;
typedef vector<VD> VVD;
int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }
struct union_find{
VI par, sz;
void init(int n){
par.resize(n);
sz.assign(n, 1);
REP(i,n) par[i] = i;
}
int find(int x){
if (par[x] == x) return x;
else return par[x] = find(par[x]);
}
bool same(int x, int y){
return find(x) == find(y);
}
void merge(int x, int y){
x = find(x);
y = find(y);
if (x == y) return;
par[x] = y;
sz[y] += sz[x];
}
int size(int x){
return sz[find(x)];
}
};
const ll mod = 1000000007;
ll add(ll x, ll y){
return (x+y)%mod;
}
ll mul(ll x, ll y){
return (x%mod)*(y%mod)%mod;
}
ll powll(ll x, ll y){
ll res = 1LL;
while(y){
if (y & 1LL)
res *= x;
res %= mod;
x = (x*x) % mod;
y >>= 1LL;
}
return res;
}
ll dfs(int now, int past, int dst, ll ma, VVL &e, VVL &c){
if (now == dst) return ma;
ll ret = 0;
REP(i,e[now].size()){
int next = e[now][i];
if (next == past) continue;
ret = max(ret, dfs(next, now, dst, max(ma, c[now][i]), e, c));
}
return ret;
}
int main() {
ll n, m, x;
cin >> n >> m >> x;
vector<pair<ll, P>> tmp(m);
REP(i,m){
ll u = in() - 1, v = in() - 1, w = in();
tmp[i] = make_pair(w, P(u, v));
}
sort(ALL(tmp));
VI u(m), v(m);
VL w(m);
REP(i,m){
u[i] = tmp[i].second.first;
v[i] = tmp[i].second.second;
w[i] = tmp[i].first;
}
ll s = 0, p = 0, ma = 0;
union_find uf;
uf.init(n);
VVL e(n), c(n);
REP(i,m){
int j = i;
while (j < m && w[j] == w[i]) j++;
ll pp = p;
// cout << i << " " << j << endl;
FOR(k,i,j-1){
if (!uf.same(u[k], v[k])) p++;
}
set<int> st;
FOR(k,i,j-1){
if (!uf.same(u[k], v[k])){
uf.merge(u[k], v[k]);
s += w[k];
pp++;
st.insert(k);
}
}
if (pp == n - 1){
ma = w[i];
break;
}
for (int k : st){
e[u[k]].push_back(v[k]);
c[u[k]].push_back(w[k]);
e[v[k]].push_back(u[k]);
c[v[k]].push_back(w[k]);
}
i = j - 1;
}
if (s > x){
cout << 0 << endl;
return 0;
}
if (s == x){
ll ans = (powll(2, p) - 2) * powll(2, m - p);
ans = ((ans % mod) + mod) % mod;
cout << ans << endl;
return 0;
}
uf.init(n);
REP(i,n){
for (int j : e[i]) uf.merge(i, j);
}
VL d(m);
REP(i,m){
if (!uf.same(u[i], v[i])){
d[i] = w[i] - ma;
}else{
d[i] = w[i] - dfs(u[i], -1, v[i], 0, e, c);
}
}
ll c1 = 0, c2 = 0;
REP(i,m){
if (d[i] == x - s) c1++;
if (d[i] > x - s) c2++;
}
ll ans = ((powll(2, c1) - 1) * powll(2, c2)) % mod;
ans = (2 * ans) % mod;
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Traveling Plan |
User |
TangentDay |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4020 Byte |
Status |
RE |
Exec Time |
102 ms |
Memory |
5888 KB |
Compile Error
./Main.cpp: In function ‘int in()’:
./Main.cpp:34:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int in() { int x; scanf("%d", &x); return x; }
^
./Main.cpp: In function ‘ll lin()’:
./Main.cpp:35:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
ll lin() { ll x; scanf("%lld", &x); return x; }
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample-01.txt, sample-02.txt, sample-03.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, sample-01.txt, sample-02.txt, sample-03.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
RE |
96 ms |
256 KB |
02.txt |
RE |
96 ms |
256 KB |
03.txt |
RE |
97 ms |
256 KB |
04.txt |
RE |
101 ms |
5888 KB |
05.txt |
RE |
96 ms |
256 KB |
06.txt |
RE |
101 ms |
5888 KB |
07.txt |
RE |
98 ms |
256 KB |
08.txt |
RE |
102 ms |
5760 KB |
09.txt |
WA |
4 ms |
5760 KB |
10.txt |
WA |
4 ms |
5760 KB |
11.txt |
WA |
4 ms |
5760 KB |
12.txt |
WA |
4 ms |
5760 KB |
sample-01.txt |
RE |
96 ms |
256 KB |
sample-02.txt |
WA |
1 ms |
256 KB |
sample-03.txt |
RE |
96 ms |
256 KB |