| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 329085 |
2020-11-19T00:47:30 Z |
evn |
Park (BOI16_park) |
C++14 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define y second
#define x first
#define pb push_back
#define mp make_pair
#define int long long
typedef long long ll;
typedef pair<ll, ll> pii;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
long double dist(pii p1, pii p2){
return sqrt(((p2.y-p1.y)*(p2.y-p1.y)) + ((p2.x-p1.x)*(p2.x-p1.x)));
}
int dsu[2100];
int sz[2100];
int find(int u){
if(dsu[u] == u){
return u;
}
return dsu[u] = find(dsu[u]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
if(a==b)return;
if(sz[b] > sz[a])swap(a,b);
//a has bigger size
dsu[b] = a;
sz[a] += sz[b];
}
bool same(int u, int v){
return find(u) == find(v);
}
bool canGet[5][5];
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, w, h;
cin >> n >> m >> w >> h;
vector<pair<pii,int>> trees;
for(int i = 0; i < n; i++){
int a, b, c;
cin >> a >> b >> c;
trees.pb({{a,b},c});
}
//borders are nodes n(top), n+1(right), n+2(down), n+3(left)
vector<pair<pii, int>> visitors;
for(int j = 0;j < m; j++){
int a, b;
cin >> a >> b;
visitors.pb({{a,b},j});
}
vector<pair<long double, pii>> edges;
//calculate the edges
for(int i = 0;i < n; i++){
//cout << trees[i].f.f << " " << trees[i].f.s << " " << trees[i].s << "\n";
for(int j = i+1;j < n; j++){
//edge between
long double distance = dist(trees[i].f, trees[j].f);
//cout << i << " " << j << " " << distance << "\n";
distance -= trees[i].s;
distance -= trees[j].s;
edges.pb({distance,{i,j}});
}
//distance to left
edges.pb({sqrt(trees[i].f.f * trees[i].f.f) - trees[i].s, {i, n+3}});
//distance to top
edges.pb({sqrt((h-trees[i].f.s)*(h-trees[i].f.s)) - trees[i].s, {i,n}});
//distance to right
edges.pb({sqrt((w-trees[i].f.f) * (w-trees[i].f.f)) - trees[i].s, {i, n+1}});
//distance to bottom
edges.pb({sqrt(trees[i].f.s * trees[i].f.s) - trees[i].s, {i,n+2}});
}
sort(edges.begin(),edges.end());
sort(visitors.begin(), visitors.end());
vector<string> answer(100005);
for(int i = 0; i <= n+3; i++){
dsu[i] = i;
sz[i] = 1;
}
int j = 0;
for(int i = 0; i < m; i++){
int ind = visitors[i].s;
while(j < edges.size() && edges[j].f <= 2*visitors[i].f.f){
//cout << edges[j].s.f << " " << edges[j].s.s << endl;
merge(edges[j].s.f, edges[j].s.s);
j++;
}
//casework
if(visitors[i].f.s == 1){
string ans = "";
ans += "1";
if(!same(n, n+2) && !same(n+1,n+2) && !same(n+3, n+2)){
ans += "2";
}
if(!same(n, n+2) && !same(n+1, n+3) && !same(n+3, n+2) && !same(n+2, n+1)){
ans += "3";
}
if(!same(n+1, n+3) && !same(n, n+3) && !same(n+2, n+3)){
ans += "4";
}
answer[ind] = ans;
}
if(visitors[i].f.s == 2){
string ans = "";
if(!same(n,n+2) && !same(n+3, n+2) && !same(n+1, n+2)){
ans += "1";
}
ans += "2";
if(!same(n+3, n+1) && !same(n,n+1) && !same(n+2, n+1)){
ans += "3";
}
if(!same(n, n+2) && !same(n+1, n+3) && !same(n+1, n+2) && !same(n, n+3)){
ans += "4";
}
answer[ind] = ans;
}
if(visitors[i].f.s == 3){
string ans = "";
if(!same(n,n+2) && !same(n+1, n+3) && !same(n, n+1) && !same(n+2, n+3)){
ans += "1";
}
if(!same(n+1, n+3) && !same(n, n+1) && !same(n+1, n+2)){
ans += "2";
}
ans += "3";
if(!same(n, n+2) && !same(n,n +1) && !same(n, n+3)){
ans += "4";
}
answer[ind] = ans;
}
if(visitors[i].f.s == 4){
string ans = "";
if(!same(n+1, n+3) && !same(n, n+3) && !same(n+2,n+3)){
ans += "1";
}
if(!same(n,n+2) && !same(n+3, n+1) && !same(n,n+3) && !same(n+1,n+2)){
ans += "2";
}
if(!same(n,n+2) && !same(n,n+3) && !same(n,n+1)){
ans += "3";
}
ans += "4";
answer[ind] = ans;
}
}
for(int i = 0; i < m ;i++){
cout << answer[i] << "\n";
}
}
Compilation message
In file included from /usr/include/c++/9/ext/pb_ds/detail/type_utils.hpp:47,
from /usr/include/c++/9/ext/pb_ds/tag_and_trait.hpp:46,
from /usr/include/c++/9/ext/pb_ds/assoc_container.hpp:46,
from park.cpp:12:
/usr/include/c++/9/tr1/type_traits:121:3: error: redefinition of 'struct std::tr1::__is_integral_helper<long long int>'
121 | _DEFINE_SPEC(0, __is_integral_helper, long long, true)
| ^~~~~~~~~~~~
/usr/include/c++/9/tr1/type_traits:117:3: note: previous definition of 'struct std::tr1::__is_integral_helper<long long int>'
117 | _DEFINE_SPEC(0, __is_integral_helper, int, true)
| ^~~~~~~~~~~~
/usr/include/c++/9/tr1/type_traits:122:3: error: redefinition of 'struct std::tr1::__is_integral_helper<long long unsigned int>'
122 | _DEFINE_SPEC(0, __is_integral_helper, unsigned long long, true)
| ^~~~~~~~~~~~
/usr/include/c++/9/tr1/type_traits:118:3: note: previous definition of 'struct std::tr1::__is_integral_helper<long long unsigned int>'
118 | _DEFINE_SPEC(0, __is_integral_helper, unsigned int, true)
| ^~~~~~~~~~~~
/usr/include/c++/9/tr1/type_traits:549:3: error: redefinition of 'struct std::tr1::__is_signed_helper<long long int>'
549 | _DEFINE_SPEC(0, __is_signed_helper, long long, true)
| ^~~~~~~~~~~~
/usr/include/c++/9/tr1/type_traits:547:3: note: previous definition of 'struct std::tr1::__is_signed_helper<long long int>'
547 | _DEFINE_SPEC(0, __is_signed_helper, int, true)
| ^~~~~~~~~~~~
/usr/include/c++/9/tr1/type_traits:564:3: error: redefinition of 'struct std::tr1::__is_unsigned_helper<long long unsigned int>'
564 | _DEFINE_SPEC(0, __is_unsigned_helper, unsigned long long, true)
| ^~~~~~~~~~~~
/usr/include/c++/9/tr1/type_traits:562:3: note: previous definition of 'struct std::tr1::__is_unsigned_helper<long long unsigned int>'
562 | _DEFINE_SPEC(0, __is_unsigned_helper, unsigned int, true)
| ^~~~~~~~~~~~
In file included from /usr/include/c++/9/tr1/functional:42,
from /usr/include/c++/9/ext/pb_ds/detail/standard_policies.hpp:51,
from /usr/include/c++/9/ext/pb_ds/assoc_container.hpp:47,
from park.cpp:12:
/usr/include/c++/9/tr1/functional_hash.h:75:3: error: redefinition of 'std::size_t std::tr1::hash<_Tp>::operator()(_Tp) const [with _Tp = long long int; std::size_t = long unsigned int]'
75 | _TR1_hashtable_define_trivial_hash(long long);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/tr1/functional_hash.h:73:3: note: 'std::size_t std::tr1::hash<_Tp>::operator()(_Tp) const [with _Tp = long long int; std::size_t = long unsigned int]' previously declared here
73 | _TR1_hashtable_define_trivial_hash(int);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/tr1/functional_hash.h:79:3: error: redefinition of 'std::size_t std::tr1::hash<_Tp>::operator()(_Tp) const [with _Tp = long long unsigned int; std::size_t = long unsigned int]'
79 | _TR1_hashtable_define_trivial_hash(unsigned long long);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/tr1/functional_hash.h:77:3: note: 'std::size_t std::tr1::hash<_Tp>::operator()(_Tp) const [with _Tp = long long unsigned int; std::size_t = long unsigned int]' previously declared here
77 | _TR1_hashtable_define_trivial_hash(unsigned int);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:71,
from park.cpp:1:
/usr/include/c++/9/functional:199:16: error: template parameter 'int _Num'
199 | template<int _Num> struct _Placeholder { };
| ^~~~
In file included from /usr/include/c++/9/ext/pb_ds/detail/standard_policies.hpp:51,
from /usr/include/c++/9/ext/pb_ds/assoc_container.hpp:47,
from park.cpp:12:
/usr/include/c++/9/tr1/functional:53:24: error: redeclared here as 'long long int <anonymous>'
53 | template<int> struct _Placeholder;
| ^~~~~~~~~~~~
park.cpp: In function 'int main()':
park.cpp:91:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | while(j < edges.size() && edges[j].f <= 2*visitors[i].f.f){
| ~~^~~~~~~~~~~~~~
