| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 385766 |
2021-04-04T23:37:15 Z |
erfanmir |
Park (BOI16_park) |
C++17 |
|
528 ms |
66368 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<int,int> 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 int MAXN = 2e3 + 10;
const int MAXLG = 18;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 8e18;
int n, m, w, h;
int par[MAXN], sz[MAXN];
ll x[MAXN], y[MAXN], r[MAXN];
int ans[4][4];
int res[MAXN];
vector<pair<ld, pii> > edge;
vector<pair<pll, int> > q;
int getroot(int v){
return par[v] == v ? v : par[v] = getroot(par[v]);
}
void merg(int v, int 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(){
int st[4];
for(int i = 0; i < 4; i++){
st[i] = getroot(n + i);
}
for(int i = 0; i < 3; i++){
ans[i][i + 1] = (st[i] != st[(i + 1) % 4]) && (st[(i + 1) % 4] != st[(i + 2) % 4]) && (st[(i + 1) % 4] != st[(i + 3) % 4]);
}
ans[0][2] = (st[0] != st[1]) && (st[2] != st[3]) && (st[0] != st[2]) && (st[1] != st[3]);
ans[1][3] = (st[0] != st[3]) && (st[2] != st[1]) && (st[0] != st[2]) && (st[1] != st[3]);
ans[0][3] = (st[3] != st[0]) && (st[0] != st[1]) && (st[0] != st[2]);
for(int i = 0; i < 4; i++){
for(int j = 0; j < 4; j++){
if(i == j){
ans[i][j] = 1;
}
if(i > j){
ans[i][j] = ans[j][i];
}
}
}
}
int main()
{
scanf("%d %d %d %d", &n, &m, &w, &h);
for(int i = 0; i < n; i++){
scanf("%lld %lld %lld\n", x + i, y + i, r + i);
ld tmp = x[i] - r[i];
tmp = max(tmp, (ld)0);
edge.push_back(mp(tmp, mp(i, n)));
tmp = w - x[i] - r[i];
tmp = max(tmp, (ld)0);
edge.push_back(mp(tmp, mp(i, n + 2)));
tmp = y[i] - r[i];
tmp = max(tmp, (ld)0);
edge.push_back(mp(tmp, mp(i, n + 1)));
tmp = h - y[i] - r[i];
tmp = max(tmp, (ld)0);
edge.push_back(mp(tmp, mp(i, n + 3)));
for(int j = 0; j < i; j++){
tmp = sqrt((ld)(x[i] - x[j]) * (x[i] - x[j]) + (ld)(y[i] - y[j]) * (y[i] - y[j])) - r[i] - r[j];
tmp = max(tmp, (ld)0);
edge.push_back(mp(tmp, mp(j, i)));
}
}
for(int i = 0; i < m; i++){
ll a, b;
scanf("%lld %lld", &a, &b);
a *= 2;
b--;
q.push_back(mp(mp(a, b), i));
}
sort(all(edge));
sort(all(q));
for(int i = 0; i < n + 4; i++){
par[i] = i;
sz[i] = 1;
}
int cnt = 0;
for(int i = 0; i < m; i++){
while(cnt < (int)edge.size() && edge[cnt].F < (ld)q[i].F.F){
merg(edge[cnt].S.F, edge[cnt].S.S);
preprocess();
cnt++;
}
for(int j = 0; j < 4; j++){
if(ans[q[i].F.S][j]){
res[q[i].S] *= 10;
res[q[i].S] += j + 1;
}
}
}
for(int i = 0; i < m; i++){
printf("%d\n", res[i]);
}
}
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:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
91 | scanf("%d %d %d %d", &n, &m, &w, &h);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
93 | scanf("%lld %lld %lld\n", x + i, y + i, r + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
park.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
114 | scanf("%lld %lld", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
515 ms |
66368 KB |
Output is correct |
| 2 |
Correct |
522 ms |
66192 KB |
Output is correct |
| 3 |
Correct |
528 ms |
66220 KB |
Output is correct |
| 4 |
Correct |
517 ms |
66192 KB |
Output is correct |
| 5 |
Correct |
526 ms |
66192 KB |
Output is correct |
| 6 |
Correct |
521 ms |
66192 KB |
Output is correct |
| 7 |
Correct |
514 ms |
66192 KB |
Output is correct |
| 8 |
Correct |
501 ms |
66192 KB |
Output is correct |
| 9 |
Correct |
2 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
48 ms |
9432 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
515 ms |
66368 KB |
Output is correct |
| 2 |
Correct |
522 ms |
66192 KB |
Output is correct |
| 3 |
Correct |
528 ms |
66220 KB |
Output is correct |
| 4 |
Correct |
517 ms |
66192 KB |
Output is correct |
| 5 |
Correct |
526 ms |
66192 KB |
Output is correct |
| 6 |
Correct |
521 ms |
66192 KB |
Output is correct |
| 7 |
Correct |
514 ms |
66192 KB |
Output is correct |
| 8 |
Correct |
501 ms |
66192 KB |
Output is correct |
| 9 |
Correct |
2 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Runtime error |
48 ms |
9432 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
