Submission #28690

#TimeUsernameProblemLanguageResultExecution timeMemory
28690AcornCkiGuiziTeam (#68)2017 Apocalypse (FXCUP2_apocalypse)C++14
1 / 1
409 ms23044 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...