| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1097827 |
2024-10-08T09:56:08 Z |
Icelast |
Park (BOI16_park) |
C++17 |
|
441 ms |
89020 KB |
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
const long double eps = 1e-9;
struct DSU{
int n;
vector<int> pa, sz;
DSU(int n) : n(n){
pa.resize(n+1);
sz.resize(n+1, 1);
for(int i = 0; i <= n; i++){
pa[i] = i;
}
};
int find(int x){
while(x != pa[x]){
x = pa[x] = pa[pa[x]];
}
return x;
}
bool same(int x, int y){
return find(x) == find(y);
}
bool merge(int x, int y){
x = find(x);
y = find(y);
if(x == y) return false;
if(sz[x] < sz[y]) swap(x, y);
pa[y] = x;
sz[x] += sz[y];
return true;
}
int size(int x){
return sz[find(x)];
}
};
struct plant{
ll x, y, r;
};
struct man{
ll t, r, id;
};
struct edge{
int u, v;
long double w;
};
void solve(){
int n, m;
cin >> n >> m;
ll w, h;
cin >> w >> h;
vector<plant> a(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i].x >> a[i].y >> a[i].r;
}
vector<man> b(m+1);
for(int i = 1; i <= m; i++){
cin >> b[i].r >> b[i].t;
b[i].id = i;
}
auto d = [&](int i, int j) -> ll{
return sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y));
};
vector<edge> pr;
for(int i = 1; i <= n; i++){
for(int j = 1; j < i; j++){
pr.push_back({i, j, d(i, j)-a[i].r-a[j].r});
}
pr.push_back({i, n+1, a[i].y-a[i].r});
pr.push_back({i, n+2, w-a[i].x-a[i].r});
pr.push_back({i, n+3, h-a[i].y-a[i].r});
pr.push_back({i, n+4, a[i].x-a[i].r});
}
sort(b.begin()+1, b.end(), [&](man a, man b){return a.r < b.r;});
sort(pr.begin(), pr.end(), [&](edge a, edge b){return a.w < b.w;});
int j = 0;
auto cmp = [&](ll a, ll b) -> bool{
return a < b;
};
int N = pr.size()+10;
DSU dsu(N);
vector<int> s;
vector<vector<int>> ans(m+1);
for(int i = 1; i <= m; i++){
while(j < pr.size() && cmp(pr[j].w, b[i].r*2)){
dsu.merge(pr[j].u, pr[j].v);
j++;
}
int id = b[i].id;
s.clear();
if(b[i].t == 1){
s.push_back(1);
if(dsu.same(n+1, n+2) || dsu.same(n+1, n+3) || dsu.same(n+1, n+4)){
}else{
s.push_back(2);
}
if(dsu.same(n+1, n+3) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4) || dsu.same(n+1, n+4)){
}else{
s.push_back(3);
}
if(dsu.same(n+1, n+4) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4)){
}else{
s.push_back(4);
}
}
if(b[i].t == 2){
s.push_back(2);
if(dsu.same(n+1, n+2) || dsu.same(n+1, n+3) || dsu.same(n+1, n+4)){
}else{
s.push_back(1);
}
if(dsu.same(n+1, n+2) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4)){
}else{
s.push_back(3);
}
if(dsu.same(n+1, n+2) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4) || dsu.same(n+1, n+3)){
}else{
s.push_back(4);
}
}
if(b[i].t == 3){
s.push_back(3);
if(dsu.same(n+1, n+3) || dsu.same(n+1, n+4) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4)){
}else{
s.push_back(1);
}
if(dsu.same(n+1, n+2) || dsu.same(n+2, n+3) || dsu.same(n+2, n+4)){
}else{
s.push_back(2);
}
if(dsu.same(n+1, n+3) || dsu.same(n+2, n+3) || dsu.same(n+3, n+4)){
}else{
s.push_back(4);
}
}
if(b[i].t == 4){
s.push_back(4);
if(dsu.same(n+1, n+4) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4)){
}else{
s.push_back(1);
}
if(dsu.same(n+1, n+2) || dsu.same(n+2, n+4) || dsu.same(n+3, n+4) || dsu.same(n+1, n+3)){
}else{
s.push_back(2);
}
if(dsu.same(n+1, n+3) || dsu.same(n+2, n+3) || dsu.same(n+3, n+4)){
}else{
s.push_back(3);
}
}
sort(s.begin(), s.end());
ans[id] = s;
}
for(int i = 1; i <= m; i++){
for(int j : ans[i]){
cout << j;
}
cout << "\n";
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
Compilation message
park.cpp: In function 'void solve()':
park.cpp:69:47: warning: narrowing conversion of '((d.solve()::<lambda(int, int)>(i, j) - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r) - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)j)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
69 | pr.push_back({i, j, d(i, j)-a[i].r-a[j].r});
| ~~~~~~~~~~~~~~^~~~~~~
park.cpp:71:37: warning: narrowing conversion of '(a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::y - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
71 | pr.push_back({i, n+1, a[i].y-a[i].r});
park.cpp:72:39: warning: narrowing conversion of '((w - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::x) - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
72 | pr.push_back({i, n+2, w-a[i].x-a[i].r});
| ~~~~~~~~^~~~~~~
park.cpp:73:39: warning: narrowing conversion of '((h - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::y) - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
73 | pr.push_back({i, n+3, h-a[i].y-a[i].r});
| ~~~~~~~~^~~~~~~
park.cpp:74:37: warning: narrowing conversion of '(a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::x - a.std::vector<plant>::operator[](((std::vector<plant>::size_type)i)).plant::r)' from 'long long int' to 'long double' [-Wnarrowing]
74 | pr.push_back({i, n+4, a[i].x-a[i].r});
park.cpp:87:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | while(j < pr.size() && cmp(pr[j].w, b[i].r*2)){
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
386 ms |
79512 KB |
Output is correct |
| 2 |
Correct |
384 ms |
78996 KB |
Output is correct |
| 3 |
Correct |
383 ms |
81044 KB |
Output is correct |
| 4 |
Correct |
380 ms |
79508 KB |
Output is correct |
| 5 |
Correct |
390 ms |
80280 KB |
Output is correct |
| 6 |
Correct |
371 ms |
79892 KB |
Output is correct |
| 7 |
Correct |
358 ms |
80792 KB |
Output is correct |
| 8 |
Correct |
350 ms |
79252 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
9420 KB |
Output is correct |
| 2 |
Correct |
46 ms |
9420 KB |
Output is correct |
| 3 |
Correct |
53 ms |
10188 KB |
Output is correct |
| 4 |
Correct |
42 ms |
10448 KB |
Output is correct |
| 5 |
Correct |
43 ms |
10444 KB |
Output is correct |
| 6 |
Correct |
41 ms |
10456 KB |
Output is correct |
| 7 |
Correct |
36 ms |
9584 KB |
Output is correct |
| 8 |
Correct |
36 ms |
9524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
386 ms |
79512 KB |
Output is correct |
| 2 |
Correct |
384 ms |
78996 KB |
Output is correct |
| 3 |
Correct |
383 ms |
81044 KB |
Output is correct |
| 4 |
Correct |
380 ms |
79508 KB |
Output is correct |
| 5 |
Correct |
390 ms |
80280 KB |
Output is correct |
| 6 |
Correct |
371 ms |
79892 KB |
Output is correct |
| 7 |
Correct |
358 ms |
80792 KB |
Output is correct |
| 8 |
Correct |
350 ms |
79252 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
42 ms |
9420 KB |
Output is correct |
| 12 |
Correct |
46 ms |
9420 KB |
Output is correct |
| 13 |
Correct |
53 ms |
10188 KB |
Output is correct |
| 14 |
Correct |
42 ms |
10448 KB |
Output is correct |
| 15 |
Correct |
43 ms |
10444 KB |
Output is correct |
| 16 |
Correct |
41 ms |
10456 KB |
Output is correct |
| 17 |
Correct |
36 ms |
9584 KB |
Output is correct |
| 18 |
Correct |
36 ms |
9524 KB |
Output is correct |
| 19 |
Correct |
426 ms |
89020 KB |
Output is correct |
| 20 |
Correct |
421 ms |
88476 KB |
Output is correct |
| 21 |
Correct |
432 ms |
88216 KB |
Output is correct |
| 22 |
Correct |
429 ms |
88108 KB |
Output is correct |
| 23 |
Correct |
441 ms |
88092 KB |
Output is correct |
| 24 |
Correct |
430 ms |
88216 KB |
Output is correct |
