CSES - Leirikisa 2 - Results
Submission details
Task:Tieverkko
Sender:Kuha
Submission time:2016-07-28 14:59:09 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED100
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.06 sdetails
#4ACCEPTED0.06 sdetails
#5ACCEPTED0.05 sdetails
#6ACCEPTED0.29 sdetails
#7ACCEPTED0.31 sdetails
#8ACCEPTED0.29 sdetails
#9ACCEPTED0.30 sdetails
#10ACCEPTED0.34 sdetails

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define LINF 999999999999999999LL
#define N (1<<17)
#define M 1000000007
using namespace std;
vector<pair<int, ll>> v[100001];
ll e[100001];
ll w[100001];
bool b[100001];
ll pot (ll k) {
if (k == 0) return 1;
if (k % 2) return (2 * pot(k - 1)) % M;
ll u = pot(k / 2);
return (u * u) % M;
}
int main () {
int n, m;
cin>>n>>m;
priority_queue<pair<ll, int>> q;
for (int i = 0; i <= n; i++) e[i] = LINF;
for (int i = 0; i < m; i++) {
int a, b;
ll c;
cin>>a>>b>>c;
v[a].push_back({b, c});
v[b].push_back({a, c});
}
q.push({0, 1});
e[1] = 0;
while (!q.empty()) {
int i = q.top().second;
ll d = -q.top().first;
q.pop();
if (b[i]) continue;
b[i] = true;
for (auto p : v[i]) {
int j = p.first;
int c = d + p.second;
if (e[j] > c) {
e[j] = c;
w[j] = 1;
q.push({-c, j});
} else if (e[j] == c) w[j]++;
}
}
ll s = 0;
for (int i : w) s += i;
ll ans = pot(m - s);
for (int i = 2; i <= n; i++) ans = (ans * (pot(w[i]) - 1)) % M;
cout<<ans<<endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
10 20
8 4 1
5 3 1
6 7 1
7 8 1
...

correct output
12096

user output
12096

Test 2

Verdict: ACCEPTED

input
10 20
5 10 1
9 10 2
1 2 1
3 4 2
...

correct output
3840

user output
3840

Test 3

Verdict: ACCEPTED

input
10 20
4 8 4
1 4 5
1 2 3
4 5 2
...

correct output
2048

user output
2048

Test 4

Verdict: ACCEPTED

input
10 20
8 9 8
4 6 6
9 6 3
9 10 1
...

correct output
3072

user output
3072

Test 5

Verdict: ACCEPTED

input
10 20
5 6 48
4 5 77
6 4 17
9 10 24
...

correct output
2048

user output
2048

Test 6

Verdict: ACCEPTED

input
100000 200000
47217 47144 1
74724 74725 1
36230 36260 1
5995 5996 1
...

correct output
741050064

user output
741050064

Test 7

Verdict: ACCEPTED

input
100000 200000
22251 22252 1
56527 56612 1
35801 35802 2
47446 47447 2
...

correct output
925428066

user output
925428066

Test 8

Verdict: ACCEPTED

input
100000 200000
21490 21480 2
6955 6956 8
3949 3938 4
71057 71058 3
...

correct output
601828864

user output
601828864

Test 9

Verdict: ACCEPTED

input
100000 200000
2001 2002 33
12041 12042 78
58901 58878 12
68010 68011 56
...

correct output
291634640

user output
291634640

Test 10

Verdict: ACCEPTED

input
100000 200000
74217 74238 380054461
43580 43581 786854520
62993 62970 636349519
63420 63478 975022059
...

correct output
215447033

user output
215447033