結果

問題 No.1950 片道きゃっちぼーる
ユーザー Mazesoba
提出日時 2022-05-21 00:33:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,990 bytes
コンパイル時間 4,363 ms
コンパイル使用メモリ 262,300 KB
最終ジャッジ日時 2025-01-29 12:22:35
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 6
権限があれば一括ダウンロードができます

ソースコード

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