結果

問題 No.1365 [Cherry 1st Tune] Whose Fault?
ユーザー SSRSSSRS
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0