結果
問題 | No.1365 [Cherry 1st Tune] Whose Fault? |
ユーザー |
|
提出日時 | 2021-01-22 22:26:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 352 ms / 2,000 ms |
コード長 | 2,879 bytes |
コンパイル時間 | 803 ms |
コンパイル使用メモリ | 87,796 KB |
最終ジャッジ日時 | 2025-01-18 04:40:16 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
#line 1 "combined.cpp"#include <algorithm>#include <cassert>#include <vector>namespace atcoder {struct dsu {public:dsu() : _n(0) {}dsu(int n) : _n(n), parent_or_size(n, -1) {}int merge(int a, int b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);int x = leader(a), y = leader(b);if (x == y) return x;if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);parent_or_size[x] += parent_or_size[y];parent_or_size[y] = x;return x;}bool same(int a, int b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);return leader(a) == leader(b);}int leader(int a) {assert(0 <= a && a < _n);if (parent_or_size[a] < 0) return a;return parent_or_size[a] = leader(parent_or_size[a]);}int size(int a) {assert(0 <= a && a < _n);return -parent_or_size[leader(a)];}std::vector<std::vector<int>> groups() {std::vector<int> leader_buf(_n), group_size(_n);for (int i = 0; i < _n; i++) {leader_buf[i] = leader(i);group_size[leader_buf[i]]++;}std::vector<std::vector<int>> result(_n);for (int i = 0; i < _n; i++) {result[i].reserve(group_size[i]);}for (int i = 0; i < _n; i++) {result[leader_buf[i]].push_back(i);}result.erase(std::remove_if(result.begin(), result.end(),[&](const std::vector<int>& v) { return v.empty(); }),result.end());return result;}private:int _n;std::vector<int> parent_or_size;};} // namespace atcoder#include <iostream>#include <iomanip>#line 71 "combined.cpp"using namespace std;using ldouble = long double;void solve() {int n;cin >> n;vector<ldouble> ds(n), ps(n);for (auto& d : ds) cin >> d;for (auto& d : ds) {ldouble b;cin >> b;d -= b;}for (auto& p : ps) {cin >> p;p = 1 / p;}ldouble ans = 0;for (int v = 0; v < n; ++v) {ans += ds[v] * ds[v] / ps[v];}atcoder::dsu dsu(n);int q;cin >> q;while (q--) {int u, v;cin >> u >> v;--u, --v;u = dsu.leader(u);v = dsu.leader(v);if (u != v) {ans -= ds[u] * ds[u] / ps[u];ans -= ds[v] * ds[v] / ps[v];auto nd = ds[u] + ds[v];auto np = ps[u] + ps[v];auto w = dsu.merge(u, v);ds[w] = nd, ps[w] = np;ans += nd * nd / np;}cout << ans << "\n";}}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);solve();return 0;}