#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1048576")
using namespace std;
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
typedef tuple <int, int, int> t3;
int IT_MAX = 1 << 17;
const ll MOD = 1000000009;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
ll mul_inv(ll a, ll b) {
ll t1 = a, t2 = b, t3;
ll v1 = 1, v2 = 0, v3;
while (t2 != 1) {
ll x = t1 / t2;
t3 = t1 - x*t2;
v3 = v1 - x*v2;
t1 = t2, t2 = t3;
v1 = v2, v2 = v3;
}
return (v2 + b) % b;
}
vector <pair<int, pii>> Ve;
ll po2[300050];
ll po2inv[300050];
ll pow2inv(ll a) {
if (a <= 300001) return po2inv[a];
return 0;
}
int r[300050];
int gsz[300050];
ll val[300050];
ll val2[300050];
int root(int x) {
return (x == r[x]) ? x : (r[x] = root(r[x]));
}
int main() {
int N, i;
scanf("%d", &N);
for (i = 1; i <= N; i++) {
int t1, t2, t3;
scanf("%d %d %d", &t1, &t2, &t3);
Ve.emplace_back(t3, pii(t1, t2));
}
ll ans = 0;
sort(all(Ve));
reverse(all(Ve));
po2[0] = 1;
for (i = 1; i <= N+1; i++) po2[i] = po2[i - 1] * 2 % MOD;
for (i = 0; i <= N + 1; i++) po2inv[i] = mul_inv(po2[i], MOD);
ll a1 = 0, a2 = 0, a3 = 0, tot = 0;
for (i = 0; i <= N; i++) r[i] = i, gsz[i] = 1;
gsz[0] = INF;
for (auto it : Ve) {
int t1 = it.second.first, t2 = it.second.second;
ll d = it.first;
int a = root(t1), b = root(t2);
ll v = pow2inv(gsz[a]) + pow2inv(gsz[b]) - pow2inv(gsz[a] + gsz[b]);
v = (v%MOD + MOD) % MOD;
// Case 1
ll u1 = (tot - val[a] - val[b]) * v;
u1 = (u1%MOD + MOD) % MOD;
a2 = (a2 + d * u1) % MOD;
// Case 2 : b
ll u2 = (pow2inv(gsz[b]) - pow2inv(gsz[a] + gsz[b])) * val2[b] + pow2inv(gsz[a]) * val[b];
u2 = (u2%MOD + MOD) % MOD;
a2 = (a2 + d * u2) % MOD;
// Case 3 : a
ll u3 = (pow2inv(gsz[a]) - pow2inv(gsz[b] + gsz[a])) * val2[a] + pow2inv(gsz[b]) * val[a];
u3 = (u3%MOD + MOD) % MOD;
a2 = (a2 + d * u3) % MOD;
a1 = (a1 + d * v) % MOD;
a3 = (a3 + d * d % MOD * v) % MOD;
tot = (tot - val[a] - val[b] + 2 * MOD) % MOD;
r[a] = b;
gsz[b] += gsz[a];
val[b] = (val[b] + val[a]) % MOD;
val[b] = (val[b] + d * v) % MOD;
tot = (tot + val[b]) % MOD;
val2[b] = (val2[b] + val2[a]) % MOD;
val2[b] = (val2[b] + d) % MOD;
}
a1 = (a1 * po2[N]) % MOD;
a2 = (a2 * po2[N]) % MOD;
a3 = (a3 * po2[N]) % MOD;
a3 = (a3 + a2 * 2) % MOD;
return !printf("%lld\n%lld\n", a1, a3);
}
Compilation message
apocalypse.cpp:23:0: warning: ignoring #pragma warning [-Wunknown-pragmas]
#pragma warning(disable:4996)
^
apocalypse.cpp:24:0: warning: ignoring #pragma comment [-Wunknown-pragmas]
#pragma comment(linker, "/STACK:1048576")
^
apocalypse.cpp: In function 'int main()':
apocalypse.cpp:86:5: warning: unused variable 'ans' [-Wunused-variable]
ll ans = 0;
^
apocalypse.cpp:79:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
apocalypse.cpp:82:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &t1, &t2, &t3);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 2 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 3 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 4 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 5 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 6 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 7 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 8 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 9 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 10 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 11 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 12 |
Correct |
0 ms |
13916 KB |
Output is correct |
| 13 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 14 |
Correct |
3 ms |
13916 KB |
Output is correct |
| 15 |
Correct |
3 ms |
13916 KB |
Output is correct |
| 16 |
Correct |
0 ms |
13744 KB |
Output is correct |
| 17 |
Correct |
3 ms |
13916 KB |
Output is correct |
| 18 |
Correct |
3 ms |
13916 KB |
Output is correct |
| 19 |
Correct |
3 ms |
13916 KB |
Output is correct |
| 20 |
Correct |
3 ms |
13916 KB |
Output is correct |
| 21 |
Correct |
103 ms |
16132 KB |
Output is correct |
| 22 |
Correct |
409 ms |
23044 KB |
Output is correct |
| 23 |
Correct |
389 ms |
23044 KB |
Output is correct |
| 24 |
Correct |
333 ms |
18436 KB |
Output is correct |
| 25 |
Correct |
383 ms |
23044 KB |
Output is correct |
| 26 |
Correct |
396 ms |
23044 KB |
Output is correct |
| 27 |
Correct |
356 ms |
23044 KB |
Output is correct |
| 28 |
Correct |
366 ms |
23044 KB |
Output is correct |
| 29 |
Correct |
349 ms |
23044 KB |
Output is correct |
| 30 |
Correct |
376 ms |
23044 KB |
Output is correct |
