結果
問題 | No.1365 [Cherry 1st Tune] Whose Fault? |
ユーザー |
|
提出日時 | 2021-06-12 13:49:34 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 757 ms / 2,000 ms |
コード長 | 1,652 bytes |
コンパイル時間 | 4,883 ms |
コンパイル使用メモリ | 161,704 KB |
実行使用メモリ | 54,272 KB |
最終ジャッジ日時 | 2024-12-16 07:51:00 |
合計ジャッジ時間 | 27,148 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
#include <bits/stdc++.h>using namespace std;int par[100001], sz[100001];int freq[100001][11][11];long long X[100001];double val[100001];double ans;int find(int x) {if(x == par[x]) return x;return par[x] = find(par[x]);}void merge(int x, int y) {if(find(x) == find(y)) return;x = find(x), y = find(y);if(sz[x] < sz[y]) swap(x, y);X[x] += X[y];par[y] = x;sz[x] += sz[y];ans -= val[x];ans -= val[y];double num = X[x], den = 0.0;bool zer = false;for(int i = 0; i <= 10; i++) {for(int j = 0; j <= 10; j++) {freq[x][i][j] += freq[y][i][j];num -= freq[x][i][j] * j;if(i)den += freq[x][i][j] * 1.0 / i;if(i == 0 && freq[x][i][j] >= 1) zer = true;}}if(den) {if(zer) val[x] = 0.0;else {ans += num * 1.0 * num / den;val[x] = num * 1.0 * num / den;}}else val[x] = 0.0;}int main() {int N; cin >> N;vector<int> A(N), B(N), P(N);for(int i = 0; i < N; i++) {cin >> A[i];}for(int i = 0; i < N; i++) {cin >> B[i];}for(int i = 0; i < N; i++) {cin >> P[i];}iota(par, par + N, 0);memset(sz, 1, sizeof(sz));for(int i = 0; i < N; i++) {X[i] = A[i];val[i] = P[i] * (A[i] - B[i]) * (A[i] - B[i]);freq[i][P[i]][B[i]] = 1;ans += val[i];}cout << setprecision(24);int Q; cin >> Q;while(Q--) {int X, Y; cin >> X >> Y;--X, --Y;merge(X, Y);cout << ans << "\n";}}