結果
問題 |
No.1950 片道きゃっちぼーる
|
ユーザー |
![]() |
提出日時 | 2022-05-20 22:56:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 903 ms / 3,000 ms |
コード長 | 1,490 bytes |
コンパイル時間 | 2,394 ms |
コンパイル使用メモリ | 220,144 KB |
最終ジャッジ日時 | 2025-01-29 11:19:13 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> #define be(v) (v).begin(),(v).end() #define pb(q) push_back(q) #define rep(i, n) for(int i=0;i<n;i++) #define all(i, v) for(auto& i : v) typedef long long ll; using namespace std; const ll mod=1000000007, INF=(1LL<<60); #define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl; void chmax(ll &a, ll b) { a = max(a, b); } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; vector<ll> a(n), x(n); rep(i, n) cin >> x[i]; rep(i, n) cin >> a[i]; vector<ll> dist(n, -1); vector<pair<ll, ll>> v; map<ll, int> mp; set<ll> s; rep(i, n) { v.push_back({a[i] + x[i], i}); mp[x[i]] = i; s.insert(x[i]); } sort(be(v)); reverse(be(v)); vector<int> seen(n, 0); vector<vector<ll>> G(n); auto f = [&](auto&& f, ll i, ll d) -> void{ // cout << i << " " << d << " " << x[i] << " " << a[i] << endl; chmax(dist[i], d); all(to, G[i]) { if(seen[to]) continue; seen[to] = 1; f(f, to, d); } return ; }; rep(i, n) { if(s.count(x[i] - a[i])) { G[mp[x[i] - a[i]]].pb(i); } if(s.count(x[i] + a[i])) { G[mp[x[i] + a[i]]].pb(i); } } for(auto [e, i] : v) { if(seen[i]) continue; seen[i] = 1; f(f, i, e); } rep(i, n) { cout << dist[i] - x[i] << endl; } return 0; }