| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 385781 |
2021-04-05T00:14:35 Z |
erfanmir |
Park (BOI16_park) |
C++11 |
|
525 ms |
70908 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 = 3e3 + 10;
const int MAXLG = 18;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 8e18;
const ld ep = 1e-12;
int n, m, w, h;
int par[MAXN], sz[MAXN];
ll x[MAXN], y[MAXN], r[MAXN];
int ans[4][4];
vector<int> res[200010];
vector<pair<ld, pii> > edge;
vector<pair<pair<ld, ll>, int> > q;
int getroot(int v){
if(par[v] == v){
return v;
}
return 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);
}
ans[0][1] = (st[0] != st[1]) && (st[1] != st[2]) && (st[1] != st[3]);
ans[1][2] = (st[1] != st[2]) && (st[2] != st[3]) && (st[2] != st[0]);
ans[2][3] = (st[2] != st[3]) && (st[3] != st[0]) && (st[3] != st[1]);
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];
edge.push_back(mp(tmp, mp(i, n)));
tmp = w - x[i] - r[i];
edge.push_back(mp(tmp, mp(i, n + 2)));
tmp = y[i] - r[i];
edge.push_back(mp(tmp, mp(i, n + 1)));
tmp = h - y[i] - r[i];
edge.push_back(mp(tmp, mp(i, n + 3)));
for(int j = 0; j < i; j++){
tmp = sqrt((ld)abs(x[i] - x[j]) * abs(x[i] - x[j]) + (ld)abs(y[i] - y[j]) * abs(y[i] - y[j])) - (ld)r[i] - (ld)r[j];
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((ld)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() && ep < q[i].F.F - edge[cnt].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].push_back(j + 1);
}
}
}
for(int i = 0; i < m; i++){
for(auto u : res[i]){
printf("%d", 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("%d %d %d %d", &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:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
113 | scanf("%lld %lld", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
518 ms |
70800 KB |
Output is correct |
| 2 |
Correct |
512 ms |
70800 KB |
Output is correct |
| 3 |
Correct |
516 ms |
70800 KB |
Output is correct |
| 4 |
Correct |
514 ms |
70908 KB |
Output is correct |
| 5 |
Correct |
514 ms |
70800 KB |
Output is correct |
| 6 |
Correct |
515 ms |
70800 KB |
Output is correct |
| 7 |
Correct |
525 ms |
70800 KB |
Output is correct |
| 8 |
Correct |
494 ms |
70832 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
13904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
518 ms |
70800 KB |
Output is correct |
| 2 |
Correct |
512 ms |
70800 KB |
Output is correct |
| 3 |
Correct |
516 ms |
70800 KB |
Output is correct |
| 4 |
Correct |
514 ms |
70908 KB |
Output is correct |
| 5 |
Correct |
514 ms |
70800 KB |
Output is correct |
| 6 |
Correct |
515 ms |
70800 KB |
Output is correct |
| 7 |
Correct |
525 ms |
70800 KB |
Output is correct |
| 8 |
Correct |
494 ms |
70832 KB |
Output is correct |
| 9 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 11 |
Incorrect |
104 ms |
13904 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
