| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 385790 |
2021-04-05T00:32:39 Z |
erfanmir |
Park (BOI16_park) |
C++17 |
|
531 ms |
89976 KB |
// In the name of god
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define lc(x) (x) << 1
#define rc(x) (x) << 1 | 1
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp make_pair
ll poww(ll a, ll b, ll md) {
ll ans = 1;
for(; b; b >>= 1, a = a * a % md){
if(b & 1){
ans = ans * a % md;
}
}
return ans % md;
}
const ll MAXN = 1e6 + 10;
const ll MAXLG = 18;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 8e18;
const ld ep = 1e-12;
ll n, m, w, h;
ll par[MAXN], sz[MAXN];
ll x[MAXN], y[MAXN], r[MAXN];
ll ans[5][5];
vector<ll> res[MAXN];
vector<pair<ld, pll> > edge;
vector<pair<pll, ll> > q;
ll getroot(ll v){
if(par[v] == v){
return v;
}
return par[v] = getroot(par[v]);
}
void merg(ll v, ll u){
v = getroot(v);
u = getroot(u);
if(v == u){
return;
}
if(sz[v] < sz[u]){
swap(v, u);
}
par[u] = v;
sz[v] += sz[u];
}
void preprocess(){
ll st[5];
for(ll i = 1; i <= 4; i++){
st[i] = getroot(n + i);
}
ans[1][2] = (st[1] != st[2]) && (st[2] != st[3]) && (st[2] != st[4]);
ans[2][3] = (st[2] != st[3]) && (st[3] != st[4]) && (st[3] != st[1]);
ans[3][4] = (st[3] != st[4]) && (st[4] != st[1]) && (st[4] != st[2]);
ans[1][3] = (st[1] != st[2]) && (st[3] != st[4]) && (st[1] != st[3]) && (st[2] != st[4]);
ans[2][4] = (st[1] != st[4]) && (st[3] != st[2]) && (st[1] != st[3]) && (st[2] != st[4]);
ans[1][4] = (st[4] != st[1]) && (st[1] != st[2]) && (st[1] != st[3]);
for(ll i = 1; i <= 4; i++){
for(ll j = 1; j <= 4; j++){
if(i == j){
ans[i][j] = 1;
}
if(i > j){
ans[i][j] = ans[j][i];
}
}
}
}
int main()
{
scanf("%lld %lld %lld %lld", &n, &m, &w, &h);
for(ll i = 0; i < n; i++){
scanf("%lld %lld %lld\n", x + i, y + i, r + i);
ld tmp = x[i] - r[i];
edge.push_back(mp(tmp, mp(i, n + 1)));
tmp = w - x[i] - r[i];
edge.push_back(mp(tmp, mp(i, n + 3)));
tmp = y[i] - r[i];
edge.push_back(mp(tmp, mp(i, n + 2)));
tmp = h - y[i] - r[i];
edge.push_back(mp(tmp, mp(i, n + 4)));
for(ll j = 0; j < i; j++){
ll dx = abs(x[i] - x[j]);
ll dy = abs(y[i] - y[j]);
tmp = sqrt(dx * dx + dy * dy) - 1.0 * r[i] - 1.0 * r[j];
edge.push_back(mp(tmp, mp(j, i)));
}
}
for(ll i = 0; i < m; i++){
ll a, b;
scanf("%lld %lld", &a, &b);
a *= 2;
q.push_back(mp(mp(a, b), i));
}
sort(all(edge));
sort(all(q));
for(ll i = 0; i < n + 4; i++){
par[i] = i;
sz[i] = 1;
}
ll cnt = 0;
for(ll i = 0; i < m; i++){
while(cnt < (ll)edge.size() && ep < q[i].F.F - edge[cnt].F){
merg(edge[cnt].S.F, edge[cnt].S.S);
preprocess();
cnt++;
}
for(ll j = 1; j <= 4; j++){
if(ans[q[i].F.S][j]){
res[q[i].S].push_back(j);
}
}
}
for(ll i = 0; i < m; i++){
for(auto u : res[i]){
printf("%lld", u);
}
printf("\n");
}
}
Compilation message
park.cpp:3: warning: ignoring #pragma comment [-Wunknown-pragmas]
3 | #pragma comment(linker, "/stack:200000000")
|
park.cpp: In function 'int main()':
park.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
95 | scanf("%lld %lld %lld %lld", &n, &m, &w, &h);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
97 | scanf("%lld %lld %lld\n", x + i, y + i, r + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
115 | scanf("%lld %lld", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
522 ms |
89616 KB |
Output is correct |
| 2 |
Correct |
518 ms |
89616 KB |
Output is correct |
| 3 |
Correct |
529 ms |
89616 KB |
Output is correct |
| 4 |
Correct |
517 ms |
89648 KB |
Output is correct |
| 5 |
Correct |
523 ms |
89616 KB |
Output is correct |
| 6 |
Correct |
529 ms |
89664 KB |
Output is correct |
| 7 |
Correct |
531 ms |
89616 KB |
Output is correct |
| 8 |
Incorrect |
506 ms |
89976 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
31576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
522 ms |
89616 KB |
Output is correct |
| 2 |
Correct |
518 ms |
89616 KB |
Output is correct |
| 3 |
Correct |
529 ms |
89616 KB |
Output is correct |
| 4 |
Correct |
517 ms |
89648 KB |
Output is correct |
| 5 |
Correct |
523 ms |
89616 KB |
Output is correct |
| 6 |
Correct |
529 ms |
89664 KB |
Output is correct |
| 7 |
Correct |
531 ms |
89616 KB |
Output is correct |
| 8 |
Incorrect |
506 ms |
89976 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
