| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1097787 |
2024-10-08T09:30:42 Z |
Bananabread |
Park (BOI16_park) |
C++17 |
|
386 ms |
73088 KB |
#include<bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;
const int maxn = 2e5 + 5;
int n, m, w,h, q;
int par[maxn], ans[maxn], x[maxn], y[maxn], r[maxn];
array<int, 3> qr[maxn];
struct iii{
ld x;
int y, z;
bool operator < (iii b) const{
return x < b.x;
}
};
vector<iii> edges;
int root(int x)
{
return par[x] < 0 ? x : par[x] = root(par[x]);
}
bool unite(int u, int v)
{
if ((u = root(u)) == (v = root(v))) return 0;
if (par[u] > par[v]) swap(u, v);
par[u] += par[v];
par[v] = u;
return 1;
}
bool same(int u, int v)
{
return root(u) == root(v);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
cin >> n >> q;
cin >> w >> h;
int w0 = n + 1, w1 = n + 2, h0 = n + 3, h1 = n + 4;
for (int i = 1; i <= n; i++)
{
cin >> x[i] >> y[i] >> r[i];
edges.push_back({x[i] - r[i], w0, i});
edges.push_back({w - x[i] - r[i], w1, i});
edges.push_back({y[i] - r[i], h0, i});
edges.push_back({h - y[i] - r[i], h1, i});
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
ld dis = sqrt(1.0 * (x[i] - x[j]) * (x[i] - x[j]) + 1.0 * (y[i] - y[j]) * (y[i] - y[j])) - (ld)r[i] - (ld)r[j];
edges.push_back({dis, i, j});
}
for (int i = 1; i <= q; i++)
cin >> qr[i][0] >> qr[i][1], qr[i][2] = i;
sort(qr + 1, qr + q + 1);
sort(edges.begin(), edges.end());
// for (auto [u, v, w] : edges) cout << u << " " <<v << " " <<w << " ????\n";
memset(par, -1, sizeof par);
for (int i = 1, pt = 0; i <= q; i++)
{
while (pt < edges.size() && edges[pt].x < (ld)2 * qr[i][0])
unite(edges[pt].y, edges[pt].z),
// cout << edges[pt].y << " " << edges[pt].z << " ???\n",
pt++;
if (qr[i][1] == 1)
{
ans[qr[i][2]] = (1 << 4) - 1;
if (same(h0, h1) || same(w0, h1) || same(w1, h1)) ans[qr[i][2]] ^= 1 << 1;
if (same(h0, h1) || same(w0, w1) || same(w0, h1) || same(w1, h0)) ans[qr[i][2]] ^= 1 << 2;
if (same(w0, w1) || same(w0, h1) || same(w0, h0)) ans[qr[i][2]] ^= 1 << 3;
}
if (qr[i][1] == 2)
{
ans[qr[i][2]] = (1 << 4) - 1;
if (same(h0, h1) || same(w1, h1) || same(w0, h1)) ans[qr[i][2]] ^= 1 << 0;
if (same(w0, w1) || same(w1, h1) || same(h0, w1)) ans[qr[i][2]] ^= 1 << 2;
if (same(h0, h1) || same(w0, w1) || same(w1, h1) || same(w0, h0)) ans[qr[i][2]] ^= 1 << 3;
}
if (qr[i][1] == 3)
{
ans[qr[i][2]] = (1 << 4) - 1;
if (same(h0, h1) || same(w0, w1) || same(w0, h1) || same(w1, h0)) ans[qr[i][2]] ^= 1 << 0;
if (same(w0, w1) || same(w1, h1) || same(h0, w1)) ans[qr[i][2]] ^= 1 << 1;
if (same(h0, h1) || same(w0, h0) || same(h0, w1)) ans[qr[i][2]] ^= 1 << 3;
}
if (qr[i][1] == 4)
{
ans[qr[i][2]] = (1 << 4) - 1;
if (same(w0, w1) || same(w0, h0) || same(w0, h1)) ans[qr[i][2]] ^= 1 << 0;
if (same(h0, h1) || same(w0, w1) || same(w1, h1) || same(w0, h0)) ans[qr[i][2]] ^= 1 << 1;
if (same(h0, h1) || same(h0, w1) || same(h0, w0)) ans[qr[i][2]] ^= 1 << 2;
}
}
for (int i = 1; i <= q; i++)
{
int x = ans[i];
for (int j = 0; j < 4; j++)
if (x >> j & 1)
cout << j + 1;
cout << "\n";
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:50:31: warning: narrowing conversion of '(x[i] - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
50 | edges.push_back({x[i] - r[i], w0, i});
| ~~~~~^~~~~~
park.cpp:51:35: warning: narrowing conversion of '((w - x[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
51 | edges.push_back({w - x[i] - r[i], w1, i});
| ~~~~~~~~~^~~~~~
park.cpp:52:31: warning: narrowing conversion of '(y[i] - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
52 | edges.push_back({y[i] - r[i], h0, i});
| ~~~~~^~~~~~
park.cpp:53:35: warning: narrowing conversion of '((h - y[i]) - r[i])' from 'long long int' to 'long double' [-Wnarrowing]
53 | edges.push_back({h - y[i] - r[i], h1, i});
| ~~~~~~~~~^~~~~~
park.cpp:69:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<iii>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | while (pt < edges.size() && edges[pt].x < (ld)2 * qr[i][0])
| ~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
381 ms |
71084 KB |
Output is correct |
| 2 |
Incorrect |
386 ms |
73088 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
14800 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
381 ms |
71084 KB |
Output is correct |
| 2 |
Incorrect |
386 ms |
73088 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
