| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1024259 |
2024-07-15T20:38:28 Z |
dpsaveslives |
Park (BOI16_park) |
C++17 |
|
241 ms |
35256 KB |
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct DSU{
int N;
vector<int> d;
void init(int n){
N = n;
d = vector<int>(N,-1);
}
int finden(int x){
if(d[x] < 0) return x;
return (d[x] = finden(d[x]));
}
bool unite(int a, int b){
a = finden(a), b = finden(b);
if(a == b) return false;
if(d[a] < d[b]) swap(a,b);
d[b] += d[a]; d[a] = b;
return true;
}
};
struct edge{
int u,v; ll w;
bool operator<(const edge &b){
return w < b.w;
}
};
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N,M; cin >> N >> M;
int W,H; cin >> W >> H;
vector<edge> edges;
vector<int> x(N+5),y(N+5),r(N+5);
for(int i = 5;i<=N+4;++i){
cin >> x[i] >> y[i] >> r[i]; edge e;
e.u = 1; e.v = i; e.w = H-y[i]-r[i]; edges.push_back(e);
e.u = 2; e.v = i; e.w = W-x[i]-r[i]; edges.push_back(e);
e.u = 3; e.v = i; e.w = y[i]-r[i]; edges.push_back(e);
e.u = 4; e.v = i; e.w = x[i]-r[i]; edges.push_back(e);
for(int j = 5;j<i;++j){
e.u = i; e.v = j; e.w = (ll)sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-r[i]-r[j];
edges.push_back(e);
}
}
sort(edges.begin(),edges.end());
DSU D; D.init(N+5);
vector<vector<int>> res(5,vector<int>(5,-1));
for(int i = 0;i<edges.size();++i){
int u = edges[i].u, v = edges[i].v;
ll w = edges[i].w;
D.unite(u,v);
for(int j = 1;j<=4;++j){
for(int k = j+1;k<=4;++k){
if(res[j][k] == -1 && D.finden(j) == D.finden(k)){
res[j][k] = res[k][j] = w;
}
}
}
}
for(int i = 0;i<M;++i){
ll rq; int en; cin >> rq >> en;
rq *= 2;
vector<bool> ok(5,true);
if(en == 1){
if(res[1][2] < rq){
ok[3] = false;
}
if(res[1][3] < rq){
ok[2] = ok[3] = false;
}
if(res[1][4] < rq){
ok[4] = false;
}
if(res[2][3] < rq){
ok[2] = false;
}
if(res[2][4] < rq){
ok[3] = ok[4] = false;
}
if(res[3][4] < rq){
ok[2] = ok[3] = ok[4] = false;
}
}
else if(en == 2){
if(res[3][4] < rq){
ok[1] = false;
}
if(res[1][2] < rq){
ok[3] = false;
}
if(res[1][4] < rq){
ok[4] = false;
}
if(res[1][3] < rq){
ok[1] = ok[4] = false;
}
if(res[2][3] < rq){
ok[1] = ok[3] = ok[4] = false;
}
if(res[2][4] < rq){
ok[3] = ok[4] = false;
}
}
else if(en == 3){
if(res[3][4] < rq){
ok[1] = false;
}
if(res[2][3] < rq){
ok[2] = false;
}
if(res[1][2] < rq){
ok[1] = ok[2] = ok[4] = false;
}
if(res[1][4] < rq){
ok[4] = false;
}
if(res[1][3] < rq){
ok[1] = ok[4] = false;
}
if(res[2][4] < rq){
ok[1] = ok[2] = false;
}
}
else{
if(res[3][4] < rq){
ok[1] = false;
}
if(res[2][3] < rq){
ok[2] = false;
}
if(res[1][2] < rq){
ok[3] = false;
}
if(res[2][4] < rq){
ok[1] = ok[2] = false;
}
if(res[1][3] < rq){
ok[2] = ok[3] = false;
}
if(res[1][4] < rq){
ok[2] = ok[3] = ok[1] = false;
}
}
for(int j = 1;j<=4;++j){
if(ok[j]) cout << j;
}
cout << "\n";
}
return 0;
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0;i<edges.size();++i){
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
35256 KB |
Output is correct |
| 2 |
Incorrect |
241 ms |
33716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
35256 KB |
Output is correct |
| 2 |
Incorrect |
241 ms |
33716 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
