結果
問題 | No.2523 Trick Flower |
ユーザー |
![]() |
提出日時 | 2023-10-27 22:30:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 269 ms / 4,000 ms |
コード長 | 1,692 bytes |
コンパイル時間 | 2,324 ms |
コンパイル使用メモリ | 204,808 KB |
最終ジャッジ日時 | 2025-02-17 15:22:50 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main(){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> C(N);for (int i = 0; i < N; i++){cin >> C[i];C[i]--;}long long SA = 0, SB = 0;for (int i = 0; i < N; i++){SA += A[i];SB += B[i];}long long tv = 0, fv = SA / SB + 1;while (fv - tv > 1){long long mid = (tv + fv) / 2;vector<long long> B2(N);for (int i = 0; i < N; i++){B2[i] = B[i] * mid;}vector<long long> A2(N);for (int i = 0; i < N; i++){A2[i] = A[i];}vector<int> in(N, 0);for (int i = 0; i < N; i++){in[C[i]]++;}queue<int> Q;for (int i = 0; i < N; i++){if (in[i] == 0){Q.push(i);}}bool ok = true;while (!Q.empty()){int v = Q.front();Q.pop();if (A2[v] < B2[v]){A2[C[v]] -= B2[v] - A2[v];}in[C[v]]--;if (in[C[v]] == 0){Q.push(C[v]);}}if (ok){for (int i = 0; i < N; i++){if (in[i] == 1){vector<int> idx = {i};while (true){int v = idx.back();in[v] = 0;if (in[C[v]] == 0){break;}v = C[v];idx.push_back(v);}long long R = 0;for (int j : idx){R += A2[j] - B2[j];}if (R < 0){ok = false;}}}}if (ok){tv = mid;} else {fv = mid;}}cout << tv << endl;}