| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 643205 |
2022-09-21T13:07:21 Z |
fatemetmhr |
Park (BOI16_park) |
C++17 |
|
6 ms |
3912 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn5 = 1e5 + 10;
const int inf = 1e9;
int par[maxn5];
vector <pair<ll, pair<int, int>>> ed, req;
vector <int> gr1[6][6], gr2[6][6];
ll x[maxn5], y[maxn5], r[maxn5];
string out[maxn5];
int get_par(int a){return par[a] == -1 ? a : par[a] = get_par(par[a]);}
inline void merge(int a, int b){
a = get_par(a); b = get_par(b);
//cout << "req a merge of " << a << ' ' << b << endl;
if(a == b)
return;
par[a] = b;
return;
}
inline ll sg(ll a){
return a / 2 + a % 2;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, m; cin >> n >> m;
ll h, w; cin >> w >> h;
ll a = inf, b = inf;
//cout << sqrt(a * a + b * b) << endl;
memset(par, -1, sizeof par);
for(int i = 0; i < n; i++){
cin >> x[i] >> y[i] >> r[i];
continue;
for(int j = 0; j < i; j++){
ll a = x[i] - x[j], b = y[i] - y[j];
ll c = sqrt(a * a + b * b);
ll need = c - r[i] - r[j];
need /= 2;
ll c2 = need * 2 + r[i] + r[j]; c2 = c2 * c2;
if(c2 != a * a + b * b)
need++;
ed.pb({need, {i, j}});
}
ed.pb({sg(x[i] - r[i]), {i, n}});
ed.pb({sg(h - y[i] - r[i]), {i, n + 1}});
ed.pb({sg(w - x[i] - r[i]), {i, n + 2}});
ed.pb({sg(y[i] - r[i]), {i, n + 3}});
}
ll red; int ent;
cin >> red >> ent;
for(int i = 0; i < n; i++)
r[i] += red;
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
ll a = x[i] - x[j], b = y[i] - y[j];
ll c = a * a + b * b;
if(c <= r[i] * r[i] + r[j] * r[j] + 2 * (r[i] + r[j]))
merge(i, j);
continue;
ll need = c - r[i] - r[j];
need /= 2;
ll c2 = need * 2 + r[i] + r[j]; c2 = c2 * c2;
if(c2 != a * a + b * b)
need++;
ed.pb({need, {i, j}});
}
if(x[i] - r[i] - red <= 0)
merge(i, n);
if(h - y[i] - r[i] - red <= 0)
merge(i, n + 1);
if(w - x[i] - r[i] - red <= 0)
merge(i, n + 2);
if(y[i] - r[i] - red <= 0)
merge(i, n + 3);
continue;
ed.pb({sg(x[i] - r[i]), {i, n}});
ed.pb({sg(h - y[i] - r[i]), {i, n + 1}});
ed.pb({sg(w - x[i] - r[i]), {i, n + 2}});
ed.pb({sg(y[i] - r[i]), {i, n + 3}});
}
gr1[1][2] = {n + 3}; gr2[1][2] = {n + 2, n + 1, n};
gr1[1][3] = {n + 3, n + 2}; gr2[1][3] = {n + 1, n};
gr1[1][4] = {n}; gr2[1][4] = {n + 2, n + 1, n + 3};
gr1[2][3] = {n + 2}; gr2[2][3] = {n + 1, n, n + 3};
gr1[2][4] = {n, n + 3}; gr2[2][4] = {n + 2, n + 1};
gr1[3][4] = {n, n + 3, n + 2}; gr2[3][4] = {n + 1};
for(int i = 1; i <= 4; i++){
if(ent == i){
cout << i;
continue;
}
int v = min(i, ent), u = max(i, ent);
bool re = true;
for(auto t1 : gr1[v][u]) for(auto t2 : gr2[v][u]) if(get_par(t1) == get_par(t2))
re = false;
if(re)
cout << i;
}
cout << endl;
return 0;
sort(all(ed));
for(int i = 0; i < m; i++){
int r, e; cin >> r >> e;
req.pb({r, {e, i}});
}
sort(all(req));
int ind = 0;
for(auto p : req){
int red = p.fi, ent = p.se.fi, id = p.se.se;
//cout << "having " << id << ' ' << red << ' ' << ent << endl;
while(ind < ed.size() && ed[ind].fi <= red){
merge(ed[ind].se.fi, ed[ind].se.se);
ind++;
}
for(int i = 1; i <= 4; i++){
if(ent == i){
out[id].pb(char(i + '0'));
continue;
}
int v = min(i, ent), u = max(i, ent);
bool re = true;
for(auto t1 : gr1[v][u]) for(auto t2 : gr2[v][u]) if(get_par(t1) == get_par(t2))
re = false;
if(re)
out[id].pb(char(i + '0'));
}
}
for(int i = 0; i < m; i++)
cout << out[i] << '\n';
}
/*
5 1
16 11
11 8 1
6 10 1
7 3 2
10 4 1
15 5 1
1 1
2 2
2 1
*/
Compilation message
park.cpp: In function 'int main()':
park.cpp:132:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | while(ind < ed.size() && ed[ind].fi <= red){
| ~~~~^~~~~~~~~~~
park.cpp:42:8: warning: unused variable 'a' [-Wunused-variable]
42 | ll a = inf, b = inf;
| ^
park.cpp:42:17: warning: unused variable 'b' [-Wunused-variable]
42 | ll a = inf, b = inf;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
3912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
