結果

問題 No.1950 片道きゃっちぼーる
ユーザー MazesobaMazesoba
提出日時 2022-05-21 00:33:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,990 bytes
コンパイル時間 4,635 ms
コンパイル使用メモリ 274,456 KB
実行使用メモリ 44,668 KB
最終ジャッジ日時 2023-10-20 15:17:10
合計ジャッジ時間 19,006 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 596 ms
44,668 KB
testcase_04 AC 609 ms
44,668 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 624 ms
44,668 KB
testcase_07 AC 541 ms
22,756 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 643 ms
29,956 KB
testcase_12 AC 578 ms
29,956 KB
testcase_13 AC 632 ms
29,884 KB
testcase_14 AC 639 ms
29,356 KB
testcase_15 WA -
testcase_16 AC 641 ms
37,012 KB
testcase_17 WA -
testcase_18 AC 566 ms
29,092 KB
testcase_19 WA -
testcase_20 AC 541 ms
22,756 KB
testcase_21 AC 635 ms
29,092 KB
testcase_22 AC 625 ms
29,092 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;

//#define DISABLE_PRINT

#if defined(ENABLE_PRINT) && !defined(DISABLE_PRINT)

#define P(...) fprintf(stderr, __VA_ARGS__)
#define P2(fmt) fprintf(stderr, fmt)
#define LP fprintf(stderr, "L: %d\n", __LINE__)

#else

#define P(...) ((void)0)
#define P2(fmt) ((void)0)
#define LP ((void)0)

#endif

#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define ALL(x) x.begin(),x.end()

using ll = long long;
using ull = unsigned long long;

int main(int, const char**)
{
    int N; cin >> N;
    vector<vector<int>> g(N);
    map<int, pair<int, int>> m;

    struct D {
        int X;
        int A;
    };
    vector<D> ins(N); 
    rep(i, N) cin >> ins[i].X;
    rep(i, N) cin >> ins[i].A;
    rep(i, N) {
        m[ins[i].X] = {i, ins[i].A};
    }
    rep(i, N) {
        auto r = ins[i].X + ins[i].A;
        if(m.find(r) != m.end()) {
            g[i].push_back(m[r].first);
            g[m[r].first].push_back(i);
        }
        auto l = ins[i].X - ins[i].A;
        if(m.find(l) != m.end()) {
            g[i].push_back(m[l].first);
            g[m[l].first].push_back(i);
        }
    }

    vector<int> ans(N, -1);

    function<void(int x, int a)> f0 = [&](int x, int a) {
        if(ans[x] != -1) return;
        ans[x] = ins[a].X + ins[a].A - ins[x].X;
        for(auto nx : g[x]) {
            f0(nx, a);
        }
    };

    vector<bool> visit(N);
    function<int(int x)> f1 = [&](int x) {
        if(visit[x]) return x;
        visit[x] = true;
        int ans = x;
        int distMax = ins[x].X + ins[x].A;
        for(auto nx : g[x]) {
            auto ta = f1(nx);
            if(ins[ta].X + ins[ta].A > distMax) {
                distMax = ins[ta].X + ins[ta].A;
                ans = ta;
            }
        }
        return ans;
    };

    rep(i, N) {
        if(ans[i] != -1) continue;
        auto a = f1(i);
        f0(i, a);
    }

    rep(i, N) cout << ans[i] << endl;

    return 0;
}
0