| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 250989 |
2020-07-19T19:05:21 Z |
luciocf |
Park (BOI16_park) |
C++14 |
|
927 ms |
24152 KB |
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 3e3+10;
const int maxq = 1e5+10;
struct Query
{
int r, e, ind;
} qry[maxq];
struct Tree
{
int x, y, r;
} tree[maxn];
struct Par
{
int u, v, k;
} par[maxn*maxn];
struct DSU
{
int pai[maxn], peso[maxn];
void init(int n)
{
for (int i = 1; i <= n; i++)
pai[i] = i, peso[i] = 1;
}
int Find(int x)
{
if (pai[x] == x) return x;
return pai[x] = Find(pai[x]);
}
void Join(int x, int y)
{
x = Find(x), y = Find(y);
if (x == y) return;
if (peso[x] < peso[y]) swap(x, y);
pai[y] = x, peso[x] += peso[y];
}
} dsu;
int n, m, w, h;
bool ans[maxq][5];
bool comp(Query a, Query b) {return a.r < b.r;}
bool comp2(Par a, Par b) {return a.k < b.k;}
ll dist(pii p1, pii p2)
{
int d1 = p1.ff-p2.ff, d2 = p1.ss-p2.ss;
return 1ll*d1*d1 + 1ll*d2*d2;
}
bool ok(int u, int v, int k, int q)
{
if (q == 0)
{
ll d = dist({tree[u].x, tree[u].y}, {tree[v].x, tree[v].y});
ll x = 1ll*(tree[u].r + tree[v].r + 2*k)*(tree[u].r + tree[v].r + 2*k);
return (x >= d);
}
int d;
if (v == n+4) d = tree[u].x;
else if (v == n+1) d = tree[u].y;
else if (v == n+2) d = w-tree[u].x;
else d = h-tree[u].y;
return (d <= tree[u].r+k);
}
int busca(int u, int v, int q)
{
int ini = 0, fim = 1e9+10, ans = 1e9+10;
while (ini <= fim)
{
int mid = (ini+fim)>>1;
if (ok(u, v, mid, q)) ans = mid, fim = mid-1;
else ini = mid+1;
}
return ans;
}
int main(void)
{
scanf("%d %d %d %d", &n, &m, &w, &h);
for (int i = 1; i <= n; i++)
scanf("%d %d %d", &tree[i].x, &tree[i].y, &tree[i].r);
for (int i = 1; i <= m; i++)
{
scanf("%d %d", &qry[i].r, &qry[i].e);
qry[i].ind = i;
}
int at = 0;
for (int i = 1; i <= n; i++)
for (int j = i+1; j <= n; j++)
par[++at] = {i, j, busca(i, j, 0)};
for (int i = 1; i <= n; i++)
for (int j = n+1; j <= n+4; j++)
par[++at] = {i, j, busca(i, j, 1)};
sort(qry+1, qry+m+1, comp);
sort(par+1, par+at+1, comp2);
dsu.init(n+4);
int ptr = 1;
for (int i = 1; i <= m; i++)
{
int R = qry[i].r, ind = qry[i].ind;
while (ptr <= at)
{
if (R >= par[ptr].k) dsu.Join(par[ptr].u, par[ptr].v), ++ptr;
else break;
}
bool lig[5][5];
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
lig[i][j] = (dsu.Find(n+i) == dsu.Find(n+j));
if (qry[i].e == 1)
{
ans[ind][1] = 1;
ans[ind][2] = (!lig[1][2] && !lig[1][3] && !lig[1][4]);
ans[ind][3] = (!lig[2][3] && !lig[2][4] && !lig[1][3] && !lig[1][4]);
ans[ind][4] = (!lig[1][4] && !lig[2][4] && !lig[3][4]);
}
else if (qry[i].e == 2)
{
ans[ind][1] = (!lig[1][2] && !lig[1][3] && !lig[1][4]);
ans[ind][2] = 1;
ans[ind][3] = (!lig[1][2] && !lig[2][3] && !lig[2][4]);
ans[ind][4] = (!lig[1][2] && !lig[1][3] && !lig[2][4] && !lig[3][4]);
}
else if (qry[i].e == 3)
{
ans[ind][1] = (!lig[2][3] && !lig[2][4] && !lig[1][3] && !lig[1][4]);
ans[ind][2] = (!lig[1][2] && !lig[2][3] && !lig[2][4]);
ans[ind][3] = 1;
ans[ind][4] = (!lig[1][3] && !lig[2][3] && !lig[3][4]);
}
else
{
ans[ind][1] = (!lig[1][4] && !lig[2][4] && !lig[3][4]);
ans[ind][2] = (!lig[1][2] && !lig[1][3] && !lig[2][4] && !lig[3][4]);
ans[ind][3] = (!lig[1][3] && !lig[2][3] && !lig[3][4]);
ans[ind][4] = 1;
}
}
for (int i = 1; i <= m; i++)
{
if (ans[i][1]) printf("1");
if (ans[i][2]) printf("2");
if (ans[i][3]) printf("3");
if (ans[i][4]) printf("4");
printf("\n");
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &n, &m, &w, &h);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &tree[i].x, &tree[i].y, &tree[i].r);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &qry[i].r, &qry[i].e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
893 ms |
24152 KB |
Output is correct |
| 2 |
Correct |
882 ms |
24056 KB |
Output is correct |
| 3 |
Incorrect |
927 ms |
24092 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
69 ms |
2680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
893 ms |
24152 KB |
Output is correct |
| 2 |
Correct |
882 ms |
24056 KB |
Output is correct |
| 3 |
Incorrect |
927 ms |
24092 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
