| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1099963 |
2024-10-12T09:24:04 Z |
InvMOD |
Park (BOI16_park) |
C++14 |
|
64 ms |
28100 KB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define gcd __gcd
#define vsz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
///#define int long long
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}
const int N = 1e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;
struct Circle{
int x,y,r;
Circle(int x = 0, int y = 0, int r = 0): x(x), y(y), r(r) {}
};
struct Edge{
int u,v,w;
Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {}
bool operator < (const Edge& q) const{
return w < q.w;
}
};
struct Query{
int id, entrance, r;
Query(int id = 0, int entrance = 0, int r = 0): id(id), entrance(entrance), r(r) {}
bool operator < (const Query &q) const{
return r < q.r;
}
};
struct DSU{
vector<int> par,sz;
DSU(int n = 0): par(n+1), sz(n+1) {
for(int i = 1; i <= n; i++){
par[i] = i;
sz[i] = 1;
}
return;
}
int asc(int x){
return x == par[x] ? x : par[x] = asc(par[x]);
}
bool join(int u, int v){
u = asc(u), v = asc(v);
if(u == v) return false;
if(sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
return true;
}
bool in(int u, int v){
return asc(u) == asc(v);
}
};
int n, q, h, w, answer[N];
vector<Edge> E;
Circle a[N]; Query Q[N];
ll square(int x){
return (1ll * x * x);
}
int calc_dist(Circle a, Circle b){
return 1ll * square(a.x - b.x) + 1ll * square(a.y - b.y) + square(a.r + b.r) - 2 * sqrt(1ll * square(a.x - b.x) + 1ll * square(a.y - b.y)) * (a.r + b.r);
}
int f(int x){
return n+x;
}
void solve()
{
cin >> n >> q >> w >> h;
for(int i = 1; i <= n; i++){
int x,y,r; cin >> x >> y >> r;
a[i] = Circle(x, y, r);
}
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
E.push_back(Edge(i, j, calc_dist(a[i], a[j])));
}
}
for(int i = 1; i <= q; i++){
int entrance,r; cin >> r >> entrance;
Q[i] = Query(i, entrance, square((r<<1)));
}
for(int i = 1; i <= n; i++){
E.push_back(Edge(i, f(1), calc_dist(a[i], Circle(0, a[i].y))));
E.push_back(Edge(i, f(2), calc_dist(a[i], Circle(a[i].x, h))));
E.push_back(Edge(i, f(3), calc_dist(a[i], Circle(w, a[i].y))));
E.push_back(Edge(i, f(4), calc_dist(a[i], Circle(a[i].x, 0))));
}
sort(all(E));
sort(Q+1, Q+1+q);
DSU dsu(f(4));
int curE = 0;
for(int i = 1; i <= q; i++){
while(curE < E.size() && E[curE].w < Q[i].r){
int u = E[curE].u, v = E[curE].v;
dsu.join(u, v);
curE = curE + 1;
}
/*
for(int x = 1; x <= 4; x++){
for(int y = x+1; y <= 4; y++){
if(dsu.in(f(x), f(y))){
cout << x <<" " << y <<"\n";
}
}
} cout <<"\n";
*/
int id = Q[i].id, cur_en = Q[i].entrance;
//check bit = 1 if can't visit that entrance
int check = 0;
if(cur_en == 1){
//Check die
if(dsu.in(f(1), f(4))){
for(int j = 1; j <= 4; j++){
if(cur_en != j){
check = check | (1<<j);
}
}
}
else{
//Check horizontal
if(dsu.in(f(1), f(3))){
check = check | (1<<3);
check = check | (1<<4);
}
//Check vertical
if(dsu.in(f(2), f(4))){
check = check | (1<<3);
check = check | (1<<2);
}
//Check virtual
if(dsu.in(f(1), f(2))){
check = check | (1<<4);
}
if(dsu.in(f(4), f(3))){
check = check | (1<<2);
}
if(dsu.in(f(3), f(2))){
check = check | (1<<3);
}
}
}
else if(cur_en == 2){
//Check die
if(dsu.in(f(3), f(4))){
for(int j = 1; j <= 4; j++){
if(cur_en != j){
check = check | (1<<j);
}
}
}
else{
//Check horizontal
if(dsu.in(f(1), f(3))){
check = check | (1<<3);
check = check | (1<<4);
}
//Check vertical
if(dsu.in(f(2), f(4))){
check = check | (1<<1);
check = check | (1<<4);
}
//Check virtual
if(dsu.in(f(1), f(4))){
check = check | (1<<1);
}
if(dsu.in(f(1), f(2))){
check = check | (1<<4);
}
if(dsu.in(f(3), f(2))){
check = check | (1<<3);
}
}
}
else if(cur_en == 3){
//Check die
if(dsu.in(f(2), f(3))){
for(int j = 1; j <= 4; j++){
if(cur_en != j){
check = check | (1<<j);
}
}
}
else{
//Check horizontal
if(dsu.in(f(1), f(3))){
check = check | (1<<1);
check = check | (1<<2);
}
//Check vertical
if(dsu.in(f(2), f(4))){
check = check | (1<<1);
check = check | (1<<4);
}
//Check virtual
if(dsu.in(f(1), f(4))){
check = check | (1<<1);
}
if(dsu.in(f(4), f(3))){
check = check | (1<<2);
}
if(dsu.in(f(1), f(2))){
check = check | (1<<4);
}
}
}
else if(cur_en == 4){
//Check die
if(dsu.in(f(1), f(2))){
for(int j = 1; j <= 4; j++){
if(cur_en != j){
check = check | (1<<j);
}
}
}
else{
//Check horizontal
if(dsu.in(f(1), f(3))){
check = check | (1<<1);
check = check | (1<<2);
}
//Check vertical
if(dsu.in(f(2), f(4))){
check = check | (1<<3);
check = check | (1<<2);
}
//Check virtual
if(dsu.in(f(1), f(4))){
check = check | (1<<1);
}
if(dsu.in(f(4), f(3))){
check = check | (1<<2);
}
if(dsu.in(f(3), f(2))){
check = check | (1<<3);
}
}
}
answer[id] = check;
}
for(int i = 1; i <= q; i++){
for(int j = 1; j <= 4; j++){
if(answer[i]>>j&1) continue;
else{
cout << j;
}
} cout <<"\n";
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#define name "InvMOD"
if(fopen(name".INP", "r")){
freopen(name".INP","r",stdin);
freopen(name".OUT","w",stdout);
}
int t = 1; //cin >> t;
while(t--) solve();
return 0;
}
Compilation message
park.cpp: In function 'void solve()':
park.cpp:124:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | while(curE < E.size() && E[curE].w < Q[i].r){
| ~~~~~^~~~~~~~~~
park.cpp: In function 'int main()':
park.cpp:298:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
298 | freopen(name".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
park.cpp:299:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
299 | freopen(name".OUT","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
27592 KB |
Output is correct |
| 2 |
Incorrect |
64 ms |
28100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
3712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
27592 KB |
Output is correct |
| 2 |
Incorrect |
64 ms |
28100 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
