結果
問題 | No.1365 [Cherry 1st Tune] Whose Fault? |
ユーザー |
![]() |
提出日時 | 2021-01-22 23:16:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 835 ms / 2,000 ms |
コード長 | 1,823 bytes |
コンパイル時間 | 2,108 ms |
コンパイル使用メモリ | 181,092 KB |
実行使用メモリ | 8,192 KB |
最終ジャッジ日時 | 2024-12-29 10:00:00 |
合計ジャッジ時間 | 31,012 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct unionfind{vector<int> p;vector<long long> S;vector<double> R;vector<bool> C;unionfind(int N, vector<long long> &S, vector<double> &R, vector<bool> &C): S(S), R(R), C(C){p = vector<int>(N, -1);}int root(int x){if (p[x] < 0){return x;} else {p[x] = root(p[x]);return p[x];}}bool same(int x, int y){return root(x) == root(y);}void unite(int x, int y){x = root(x);y = root(y);if (x != y){if (p[x] > p[y]){swap(p[x], p[y]);}p[x] += p[y];p[y] = x;S[x] += S[y];R[x] += R[y];if (C[y]){C[x] = true;}}}double cost(int x){x = root(x);if (C[x]){return 0;} else {return S[x] * S[x] / R[x];}}};int main(){cout << fixed << setprecision(20);int N;cin >> N;vector<int> A(N);for (int i = 0; i < N; i++){cin >> A[i];}vector<int> B(N);for (int i = 0; i < N; i++){cin >> B[i];}vector<int> P(N);for (int i = 0; i < N; i++){cin >> P[i];}vector<long long> D(N);for (int i = 0; i < N; i++){D[i] = A[i] - B[i];}vector<double> R(N, 1);for (int i = 0; i < N; i++){if (P[i] != 0){R[i] = (double) 1 / P[i];}}vector<bool> zero(N, false);for (int i = 0; i < N; i++){if (P[i] == 0){zero[i] = true;}}unionfind UF(N, D, R, zero);double ans = 0;for (int i = 0; i < N; i++){ans += UF.cost(i);}int Q;cin >> Q;for (int i = 0; i < Q; i++){int X, Y;cin >> X >> Y;X--;Y--;if (!UF.same(X, Y)){ans -= UF.cost(X);ans -= UF.cost(Y);UF.unite(X, Y);ans += UF.cost(X);}cout << ans << endl;}}