結果
問題 |
No.1950 片道きゃっちぼーる
|
ユーザー |
|
提出日時 | 2023-07-17 15:13:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,958 bytes |
コンパイル時間 | 1,266 ms |
コンパイル使用メモリ | 119,628 KB |
最終ジャッジ日時 | 2025-02-15 15:25:28 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 8 WA * 15 |
ソースコード
/* to do 有効グラフ */ #include<iostream> #include<set> #include<algorithm> #include<vector> #include<string> #include<set> #include<map> #include<numeric> #include<queue> #include<cmath> #include <unordered_set> using namespace std; typedef long long ll; const ll INF=1LL<<60; typedef pair<ll,ll> P; typedef pair<int,P> PP; const ll MOD=1e9+7; int main(){ int N; cin>>N; map<int,int> mp; vector<ll> X(N); vector<ll> A(N); for(int i=0;i<N;i++){ cin>>X[i]; } for(int i=0;i<N;i++){ cin>>A[i]; } for(int i=0;i<N;i++){ mp[X[i]]=i;//X[i]に人iがいる } vector<vector<int>> G(N),rG(N); for(int i=0;i<N;i++){ //i番目の人から辺を張る if(mp.count(X[i]+A[i])){ int j=mp[X[i]+A[i]]; G[i].push_back(j); rG[j].push_back(i); } if(mp.count(X[i]-A[i])){ int j=mp[X[i]-A[i]]; G[i].push_back(j); rG[j].push_back(i); } } vector<bool> visit(N,false); vector<bool> seen(N,false); vector<bool> finish(N,false); vector<ll> dist(N,0); for(int i=0;i<N;i++){ dist[i]=X[i]+A[i]; } auto dfs=[&](auto f,int now)->ll{ //cout<<"now="<<now<<endl; if(seen[now] && !finish[now]){ finish[now]=true; return dist[now]; } seen[now]=true; for(int to:G[now]){ if(finish[to]) continue; dist[now]=max(dist[now],f(f,to)); } finish[now]=true; return dist[now]; }; for(int i=0;i<N;i++){ if(!seen[i]){ //cout<<"i="<<i<<endl; dfs(dfs,i); } } vector<ll> ans(N); for(int i=0;i<N;i++){ //i番目の人間が直接投げるか ans[i]=dist[i]-X[i]; } for(ll v:ans){ cout<<v<<endl; } }