oj.uz

Submission #720749

# Submission time Handle Problem Language Result Execution time Memory
720749 2023-04-09T09:14:58 Z hgmhc 개구리 (KOI13_frog) C++17
22 / 22
 69 ms 2428 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 1 ms 1084 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct

Subtask #2
2.64 / 2.64

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1088 KB Output is correct
2 Correct 2 ms 980 KB Output is correct
3 Correct 1 ms 1096 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct

Subtask #3
3.52 / 3.52

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1084 KB Output is correct
2 Correct 1 ms 1088 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 1 ms 1092 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct

Subtask #4
4.18 / 4.18

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1096 KB Output is correct
2 Correct 4 ms 1108 KB Output is correct
3 Correct 4 ms 1236 KB Output is correct
4 Correct 5 ms 1168 KB Output is correct
5 Correct 5 ms 1232 KB Output is correct
6 Correct 7 ms 1228 KB Output is correct
7 Correct 5 ms 1224 KB Output is correct

Subtask #5
4.62 / 4.62

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1236 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 4 ms 1108 KB Output is correct
4 Correct 5 ms 1236 KB Output is correct
5 Correct 7 ms 1236 KB Output is correct
6 Correct 10 ms 1432 KB Output is correct
7 Correct 18 ms 1960 KB Output is correct

Subtask #6
5.06 / 5.06

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1560 KB Output is correct
2 Correct 40 ms 2172 KB Output is correct
3 Correct 62 ms 2368 KB Output is correct
4 Correct 56 ms 2376 KB Output is correct
5 Correct 57 ms 2388 KB Output is correct
6 Correct 62 ms 2424 KB Output is correct
7 Correct 69 ms 2428 KB Output is correct