結果
問題 | No.2523 Trick Flower |
ユーザー |
|
提出日時 | 2023-10-27 22:44:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,238 bytes |
コンパイル時間 | 860 ms |
コンパイル使用メモリ | 74,760 KB |
実行使用メモリ | 11,004 KB |
最終ジャッジ日時 | 2024-09-25 14:44:51 |
合計ジャッジ時間 | 3,214 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 WA * 1 |
ソースコード
#include<iostream>#include<vector>#include<cassert>using namespace std;int N,A[1<<17],B[1<<17],C[1<<17];long need[1<<17];int deg[1<<17];bool vis[1<<17];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>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>>C[i],C[i]--;deg[C[i]]++;}vector<int>Q;for(int i=0;i<N;i++)if(!deg[i])Q.push_back(i);for(int i=0;i<Q.size();i++){int u=Q[i];vis[u]=true;if(!--deg[C[u]])Q.push_back(C[u]);}vector<vector<int> >Lp;for(int i=0;i<N;i++)if(!vis[i]){int u=i;Lp.push_back(vector<int>());while(!vis[u]){Lp.back().push_back(u);vis[u]=true;u=C[u];}}long L=0,R=1e15;while(R-L>1){long k=(L+R)/2;bool out=false;for(int i=0;i<N;i++){if(k&&B[i]&&B[i]>(long)1e15/k){out=true;break;}need[i]=k*B[i];}if(out){R=k;continue;}for(int u:Q){need[C[u]]+=max(need[u]-A[u],0L);}for(int i=0;i<Lp.size();i++){long sN=0,sA=0;for(int u:Lp[i]){sN+=need[u];sA+=A[u];if(sN>(long)1e15)break;}if(sN>sA){out=true;break;}}if(out)R=k;else L=k;}cout<<L<<endl;}