| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 524262 |
2022-02-09T00:19:11 Z |
vijay |
Park (BOI16_park) |
C++17 |
|
0 ms |
204 KB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <cmath>
#include <bitset>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
#define trav(a, x) for (auto& a: x)
#define all(x) begin(x), end(x)
#define mp make_pair
#define pb push_back
#define f first
#define s second
struct DSU {
vector<int> e;
DSU(int N) { e = vector<int>(N, -1); }
// get representive component (uses path compression)
int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
bool same_set(int a, int b) { return get(a) == get(b); }
int size(int x) { return -e[get(x)]; }
bool unite(int x, int y) { // union by size
x = get(x), y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y]; e[y] = x;
return true;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ifstream cin;
// cin.open("test.in");
int n, m; cin >> n >> m;
int w, h; cin >> w >> h;
vector<pair<int, pair<ll, ll> > > trees;
for(int i = 0; i < n; i++){
int x, y, radius; cin >> x >> y >> radius;
trees.pb(mp(radius, mp(x, y)));
}
vector<pair<int, pair<ll, int> > > visitors;
for(int i = 0; i < m; i++){
int radius, entrance; cin >> radius >> entrance;
visitors.pb(mp(radius, mp(entrance, i)));
}
sort(visitors.begin(), visitors.end());
// edge codes: left: n, right: n + 1, bottom: n + 2, top: n + 3
// edges
vector<pair<double, pair<int, int> > > edges;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
double dist = sqrt(pow(trees[i].s.f - trees[j].s.f, 2) + pow(trees[i].s.s - trees[j].s.s, 2)) - trees[i].f - trees[j].f;
edges.pb(mp(dist, mp(i, j)));
}
// how to figure out the distance between the edges of the share itself
edges.pb(mp(trees[i].s.f - trees[i].f, mp(i, n)));
edges.pb(mp(w - trees[i].s.f - trees[i].f, mp(i, n + 1)));
edges.pb(mp(trees[i].s.s - trees[i].f, mp(i, n + 2)));
edges.pb(mp(h - trees[i].s.s - trees[i].f, mp(i, n + 3)));
}
sort(edges.begin(), edges.end());
// for(auto& edge: edges){
// if(edge.s.s == n){
// cout << edge.f << " " << edge.s.f << " " << edge.s.s << "\n";
// }
// }
vector<string> ans(m);
int left = n; int right = n + 1; int bottom = n + 2; int top = n + 3;
DSU dsu(n + 5);
int edgesIndex = 0;
for(int i = 0; i < m; i++){
while(true){
dsu.unite(edges[edgesIndex].s.f, edges[edgesIndex].s.s);
// cout << "uniting " << edges[edgesIndex].s.f << " " << edges[edgesIndex].s.s << " with value " << 2*visitors[i].f << "\n";
edgesIndex++;
if(edgesIndex == edges.size() || edges[edgesIndex].f > 2*visitors[i].f){
// cout << " break " << edges[edgesIndex].f << " " << visitors[i].f << "\n";
break;
}
}
// cout << "EDGE " << edgesIndex << " " << edges[edgesIndex].f << " " << visitors[i].f << "\n";
// which ones should work for this?
string output = "";
if(visitors[i].s.f == 1){
output += "1";
if(!dsu.same_set(left, bottom) && !dsu.same_set(bottom, right) && !dsu.same_set(bottom, top)){
output += "2";
}
if(!dsu.same_set(left, bottom) && !dsu.same_set(top, right) && !dsu.same_set(left, right)){
output += "3";
}
if(!dsu.same_set(left, bottom) && !dsu.same_set(top, left) && !dsu.same_set(left, right)){
output += "4";
}
// cout << dsu.same_set(left, bottom) << dsu.same_set(top, left) << dsu.same_set(bottom, top) << "\n";
} else if (visitors[i].s.f == 2){
if(!dsu.same_set(bottom, right) && !dsu.same_set(bottom, top) && !dsu.same_set(left, bottom)){
output += "1";
}
output += "2";
if(!dsu.same_set(bottom, right) && !dsu.same_set(top, right) && !dsu.same_set(left, right)){
output += "3";
}
if(!dsu.same_set(bottom, right) && !dsu.same_set(top, left) && !dsu.same_set(bottom, top)){
output += "4";
}
} else if (visitors[i].s.f == 3){
if(!dsu.same_set(left, bottom) && !dsu.same_set(top, right) && !dsu.same_set(left, right)){
output += "1";
}
if(!dsu.same_set(bottom, right) && !dsu.same_set(top, right) && !dsu.same_set(bottom, top)){
output += "2";
}
output += "3";
if(!dsu.same_set(top, right) && !dsu.same_set(top, left) && !dsu.same_set(bottom, top)){
output += "4";
}
} else {
if(!dsu.same_set(left, bottom) && !dsu.same_set(top, left) && !dsu.same_set(left, right)){
output += "1";
}
if(!dsu.same_set(bottom, right) && !dsu.same_set(top, left) && !dsu.same_set(bottom, top)){
output += "2";
}
if(!dsu.same_set(top, right) && !dsu.same_set(top, left) && !dsu.same_set(bottom, top)){
output += "3";
}
output += "4";
}
ans[visitors[i].s.s] = output;
}
for(auto& a: ans){
cout << a << '\n';
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:103:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | if(edgesIndex == edges.size() || edges[edgesIndex].f > 2*visitors[i].f){
| ~~~~~~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
