Submission #720749

#	Time	Username	Problem	Language	Result	Execution time	Memory
720749		hgmhc	개구리 (KOI13_frog)	C++17	22 / 22	69 ms	2428 KiB

frog

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)

template <const int N>
struct disjoint_set {
    int p[N], s[N];
    disjoint_set() { iota(p,p+N,0), fill(s,s+N,1); }
    int find(int x) {
        assert(x < N);
        if (x == p[x]) return x;
        return p[x] = find(p[x]);
    }
    void merge(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return;
        if (s[a] > s[b]) swap(a,b);
        s[b] += s[a], p[a] = b;
    }
    int size(int x) {
        return s[find(x)];
    }
    bool same(int a, int b) {
        return find(a) == find(b);
    }
};

const int N = 1e5+3;
int n, R, d;
using P = pair<ii,int>;
P p[N];
disjoint_set<N> ds;

void solve() {
    sort(p+1,p+n+1);
    auto cmp = [](const P &x, const P &y) {
        return make_pair(x.fi.se,x.se) < make_pair(y.fi.se,y.se);
    };
    set<P,bool(*)(const P&,const P&)> s(cmp);
    // x좌표가 [x,x+r]에 포함됨 / 정렬은 y좌표의 오름차순으로 / 가장 앞쪽 세 개만 추가한다(자신이 포함되어 있을 수 있으므로)
    int l = 1, r = 0;
    rep(i,1,n) {
        auto [x,y] = p[i].fi;
        while (r < n and p[r+1].fi.fi <= x+R) s.insert(p[++r]);
        while (l <= r and p[l].fi.fi < x) s.erase(p[l++]);
        auto it = s.lower_bound({ii{-1,y+R},0});
        rep(j,1,3) {
            if (it != end(s) and it->fi.se <= y+R+d)
                ds.merge(it->se,p[i].se), it++;
        }
        it = s.upper_bound({ii{-1,y-R},1e9});
        rep(j,1,3) {
            if (it != begin(s)) {
                if ((--it)->fi.se >= y-d-R)
                    ds.merge(it->se,p[i].se);
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &R);
    rep(i,1,n) scanf("%d%d", &p[i].fi.fi, &p[i].fi.se), p[i].se = i;
    rep(i,1,n) if (p[i].fi == ii{0,0}) swap(p[1].fi,p[i].fi);
    scanf("%d", &d);
    solve();
    rep(i,1,n) swap(p[i].fi.fi,p[i].fi.se);
    solve();
    int ans = 0;
    rep(i,1,n) if (ds.same(1,p[i].se)) Mup(ans,p[i].fi.fi+p[i].fi.se+R+R);
    printf("%d", ans);
}

Compilation message (stderr)

frog.cpp: In function 'int main()':
frog.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d%d", &n, &R);
      |     ~~~~~^~~~~~~~~~~~~~~~
frog.cpp:71:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     rep(i,1,n) scanf("%d%d", &p[i].fi.fi, &p[i].fi.se), p[i].se = i;
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
frog.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d", &d);
      |     ~~~~~^~~~~~~~~~

• Subtask 1: 1.98 / 1.98
• Subtask 2: 2.64 / 2.64
• Subtask 3: 3.52 / 3.52
• Subtask 4: 4.18 / 4.18
• Subtask 5: 4.62 / 4.62
• Subtask 6: 5.06 / 5.06