| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 351793 |
2021-01-20T07:55:04 Z |
8e7 |
Park (BOI16_park) |
C++14 |
|
777 ms |
49828 KB |
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#define maxn 2005
#define pii pair<int, int>
#define ff first
#define ss second
#define ll long long
using namespace std;
pii pos[maxn];
int rad[maxn], par[maxn], val[4][4], mv[4], cross, c1, c2;
bool done[4][4], ans[4];
const int ls = maxn - 1, rs = maxn - 2, us = maxn - 3, ds = maxn - 4;
inline int dist(int x, int y) {
ll d = (ll)(pos[x].ff - pos[y].ff) * (pos[x].ff - pos[y].ff) + (ll)(pos[x].ss - pos[y].ss) * (pos[x].ss - pos[y].ss);
ll s = sqrt(d);
return (s - rad[x] - rad[y]) / 2 + 1;
}
struct edge{
int u, v, d;
edge(int a, int b, int c) {
u = a, v = b, d = c;
}
};
vector<edge> ed;
inline bool cmp(edge a, edge b) {
return a.d < b.d;
}
inline int find(int a) {
return a == par[a] ? a : (par[a] = find(par[a]));
}
void Union(int a, int b) {
par[find(a)] = find(b);
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
int n, m, w, h;
cin >> n >> m >> w >> h;
for (int i = 0;i < maxn;i++) par[i] = i;
for (int i = 0;i < 4;i++) mv[i] = 2147483647;
for (int i = 0;i < n;i++) {
cin >> pos[i].ff >> pos[i].ss >> rad[i];
}
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
ed.push_back(edge(i, j, dist(i, j)));
}
ed.push_back(edge(i, ls, (pos[i].ff - rad[i]) / 2 + 1));
ed.push_back(edge(i, rs, (w - (pos[i].ff + rad[i])) / 2 + 1));
ed.push_back(edge(i, us, (pos[i].ss - rad[i]) / 2 + 1));
ed.push_back(edge(i, ds, (h - (pos[i].ss + rad[i])) / 2 + 1));
}
sort(ed.begin(), ed.end(), cmp);
for (int i = 0;i < ed.size();i++) {
Union(ed[i].u, ed[i].v);
if (ed[i].v > n) {
for (int j = 1;j <= 4;j++) {
for (int k = j + 1;k <= 4;k++) {
if (!done[j - 1][k - 1] && find(maxn - j) == find(maxn - k)) {
val[j - 1][k - 1] = ed[i].d;
done[j - 1][k - 1] = 1;
}
}
}
}
}
for (int i = 0;i < 4;i++) {
for (int j = i + 1;j < 4;j++) {
mv[i] = min(mv[i], val[i][j]);
mv[j] = min(mv[j], val[i][j]);
}
}
cross = min(val[0][1], val[2][3]);
c1 = min(val[0][2], val[1][3]);
c2 = min(val[1][2], val[0][3]);
//cout << cross << " " << c1 << " " << c2 << endl;
for (int i = 0;i < m;i++) {
int r, e;
cin >> r >> e;
ans[0] = ans[1] = ans[2] = ans[3] = 0;
ans[e - 1] = 1;
if (e == 1) {
if (mv[2] > r) ans[1] = 1;
if (mv[0] > r) ans[3] = 1;
if (min(cross, c1) > r) ans[2] = 1;
} else if (e == 2) {
if (mv[2] > r) ans[0] = 1;
if (mv[1] > r) ans[2] = 1;
if (min(cross, c2) > r) ans[3] = 1;
} else if (e == 3) {
if (mv[1] > r) ans[1] = 1;
if (mv[3] > r) ans[3] = 1;
if (min(cross, c1) > r) ans[0] = 1;
} else{
if (mv[0] > r) ans[0] = 1;
if (mv[3] > r) ans[2] = 1;
if (min(cross, c2) > r) ans[1] = 1;
}
for (int j = 0;j < 4;j++) {
if (ans[j]) cout << j + 1;
}
cout << "\n";
}
}
/*
5 3
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
1 10
5 5
3 3 1
1 1
d3c
0 1
a2b
*/
Compilation message
park.cpp: In function 'int main()':
park.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for (int i = 0;i < ed.size();i++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
777 ms |
49828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
1636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
777 ms |
49828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
