結果
問題 | No.1950 片道きゃっちぼーる |
ユーザー | kwm_t |
提出日時 | 2022-05-21 01:49:22 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,666 ms / 3,000 ms |
コード長 | 2,014 bytes |
コンパイル時間 | 2,666 ms |
コンパイル使用メモリ | 228,604 KB |
実行使用メモリ | 134,880 KB |
最終ジャッジ日時 | 2023-10-20 15:27:26 |
合計ジャッジ時間 | 19,785 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
17,620 KB |
testcase_01 | AC | 8 ms
17,624 KB |
testcase_02 | AC | 8 ms
17,620 KB |
testcase_03 | AC | 587 ms
97,160 KB |
testcase_04 | AC | 591 ms
97,160 KB |
testcase_05 | AC | 8 ms
17,620 KB |
testcase_06 | AC | 460 ms
59,180 KB |
testcase_07 | AC | 851 ms
134,880 KB |
testcase_08 | AC | 1,666 ms
134,872 KB |
testcase_09 | AC | 626 ms
96,684 KB |
testcase_10 | AC | 632 ms
91,548 KB |
testcase_11 | AC | 713 ms
99,732 KB |
testcase_12 | AC | 653 ms
99,732 KB |
testcase_13 | AC | 530 ms
77,792 KB |
testcase_14 | AC | 451 ms
62,340 KB |
testcase_15 | AC | 1,388 ms
97,160 KB |
testcase_16 | AC | 473 ms
59,180 KB |
testcase_17 | AC | 8 ms
17,620 KB |
testcase_18 | AC | 711 ms
109,172 KB |
testcase_19 | AC | 1,359 ms
97,156 KB |
testcase_20 | AC | 732 ms
99,732 KB |
testcase_21 | AC | 478 ms
65,712 KB |
testcase_22 | AC | 481 ms
65,712 KB |
ソースコード
#include <bits/stdc++.h> //#include <atcoder/all> using namespace std; //using namespace atcoder; //using mint = modint1000000007; //const int mod = 1000000007; //using mint = modint998244353; //const int mod = 998244353; //const int INF = 1e9; //const long long LINF = 1e18; #define rep(i, n) for (int i = 0; i < (n); ++i) #define rep2(i,l,r)for(int i=(l);i<(r);++i) #define rrep(i, n) for (int i = (n-1); i >= 0; --i) #define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i) #define all(x) (x).begin(),(x).end() #define allR(x) (x).rbegin(),(x).rend() #define endl "\n" #define P pair<int,int> template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; } template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; } map<long long, int> Compless(const vector<long long> &v) { vector<long long>vv = v; sort(all(vv)); vv.erase(unique(all(vv)), vv.end()); map<long long, int>mp; rep(i, vv.size()) mp[vv[i]] = i; return mp; } vector<int>to[600005]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long>x(n), a(n); rep(i, n)cin >> x[i]; rep(i, n)cin >> a[i]; set<long long>st; rep(i, n) { st.insert(x[i]); st.insert(x[i] + a[i]); st.insert(x[i] - a[i]); } vector<long long>v; for (auto e : st)v.push_back(e); auto mp = Compless(v); rep(i, n) { long long s = x[i]; long long t = x[i] + a[i]; long long u = x[i] - a[i]; to[mp[t]].push_back(mp[s]); to[mp[u]].push_back(mp[s]); } vector<long long>d = v; priority_queue<pair<long long, int>>pq; rep(i, d.size()) pq.push({ d[i],i }); while (!pq.empty()) { auto top = pq.top(); long long dist = top.first; long long pos = top.second; pq.pop(); if (d[pos] > dist)continue; for (auto npos : to[pos]) { if (chmax(d[npos], d[pos])) { pq.push({ d[npos],npos }); } } } rep(i, n) { long long ans = d[mp[x[i]]] - x[i]; cout << ans << endl; } return 0; }