| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 720731 |
2023-04-09T07:08:16 Z |
hgmhc |
개구리 (KOI13_frog) |
C++17 |
|
48 ms |
2484 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,5) {
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,5) {
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[n].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:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%d", &d);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
980 KB |
Output is correct |
| 2 |
Correct |
1 ms |
980 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
1760 KB |
Output is correct |
| 2 |
Incorrect |
48 ms |
2484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
