| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 937454 |
2024-03-04T05:51:23 Z |
Amaarsaa |
Park (BOI16_park) |
C++14 |
|
357 ms |
68024 KB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long ;
using pll = pair < ll, ll >;
bool B[5][4002] = {false};
bool D[5][5] = {false};
ll ataman[2002];
ll Get(ll x) {
if ( x == ataman[x]) return x;
return ataman[x] = Get(ataman[x]);
}
void Unite(int x, int y) {
x = Get(x);
y = Get(y);
if ( x == y) return ;
ataman[x] = y;
for ( int i = 1; i <= 4; i ++) B[i][y] |= B[i][x];
for (int j = 1; j <= 4; j ++) {
for (int i1 = j + 1; i1 <= 4; i1 ++) {
if ( B[j][y] && B[i1][y]) D[j][i1] = 1;
}
}
return ;
}
ll x[2002], y[2002], r[2002];
priority_queue < pll , vector <pll> , greater<pll> > Durvuntal[5];
int main() {
ll n, m, i, j, N, M, x1, Y, y1, R, ind, i1, ans;
cin >> n >> m;
cin >> N >> M;
for (i = 1; i <= n; i ++) ataman[i] = i;
for (i = 1; i <= n; i ++) {
cin >> x[i] >> y[i] >> r[i];
}
vector < pair <long double, pair < ll, ll> > > v;
for (i = 1; i <= n; i ++) {
Durvuntal[1].push({y[i] - r[i], i});
Durvuntal[2].push({N - (x[i] + r[i]), i});
Durvuntal[3].push({M - (y[i] + r[i]), i});
Durvuntal[4].push({x[i] - r[i], i});
for (j = i+ 1; j <= n; j ++) {
long double S = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
S = sqrt(S);
S = S - r[i] - r[j];
v.push_back({S, {i, j}});
}
}
sort(v.begin(), v.end());
vector < pair < ll, pair < ll, ll > > > Q;
for (i = 1; i <= m; i ++) {
cin >> x1 >> y1;
Q.push_back({x1, {y1, i}});
}
sort(Q.begin(), Q.end());
string Ans[5];
ind= 0;
for (pair < ll, pair < ll, ll > >& P : Q) {
long double S = P.first * 2.0;
for (i = 1; i <= 4; i ++) {
while(!Durvuntal[i].empty()) {
pll Pa = Durvuntal[i].top();
if (Pa.first < S) {
Durvuntal[i].pop();
// cout << i << " " << Pa.first << endl;
R = Get(Pa.second);
B[i][R] = 1;
for (j = 1; j <= 4; j ++) {
for (i1 = j + 1; i1 <= 4; i1 ++) {
if ( B[j][R] && B[i1][R]) D[j][i1] = 1;
}
}
}
else break;
}
}
while ( ind < v.size() && v[ind].first < S) {
// cout << v[ind].first << " " << v[ind].second.first << " " << v[ind].second.second << endl;
Unite(v[ind].second.first, v[ind].second.second);
ind ++;
}
Y = P.second.first;
if ( Y == 1) {
ans = 1;
if ( !D[1][4] && !D[1][2] && !D[1][3]) ans = ans * 10 + 2;
if ( !D[1][4] && !D[2][3] && !D[1][3] && !D[2][4]) ans = ans * 10 + 3;
if ( !D[1][4] && !D[3][4] && !D[2][4]) ans = ans * 10 + 4;
}
if ( Y == 2) {
ans = 2;
if ( !D[1][4] && !D[1][2] && !D[1][3]) ans = ans * 10 + 1;
if ( !D[1][2] && !D[2][3] && !D[2][4]) ans = ans * 10 + 3;
if ( !D[1][2] && !D[3][4] && !D[2][4] && !D[1][3]) ans = ans * 10 + 4;
}
if ( Y == 3) {
ans = 3;
if ( !D[1][4] && !D[2][3] && !D[1][3] && !D[2][4]) ans = ans * 10 + 1;
if ( !D[1][2] && !D[2][3] && !D[2][4]) ans = ans * 10 + 2;
if ( !D[2][3] && !D[3][4] && !D[1][3]) ans = ans * 10 + 4;
}
if ( Y == 4) {
ans = 4;
if ( !D[1][4] && !D[3][4] && !D[2][4]) ans = ans * 10 + 1;
if ( !D[1][2] && !D[3][4] && !D[2][4] && !D[1][3]) ans = ans * 10 + 2;
if ( !D[2][3] && !D[3][4] && !D[1][3]) ans = ans * 10 + 3;
}
string str = to_string(ans);
sort(str.begin(), str.end());
Ans[P.second.second] = str;
/*
for (i = 1; i <= 4; i ++) {
for (j = i + 1; j <= 4; j ++) {
cout << D[i][j] << " ";
}
cout << endl;
}
*/
}
for (i = 1; i <= m; i ++) {
cout << Ans[i] << endl;
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:82:15: warning: comparison of integer expressions of different signedness: 'll' {aka '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]
82 | while ( ind < v.size() && v[ind].first < S) {
| ~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
357 ms |
67500 KB |
Output is correct |
| 2 |
Correct |
355 ms |
68024 KB |
Output is correct |
| 3 |
Correct |
350 ms |
67764 KB |
Output is correct |
| 4 |
Correct |
354 ms |
66976 KB |
Output is correct |
| 5 |
Correct |
350 ms |
67256 KB |
Output is correct |
| 6 |
Correct |
354 ms |
66208 KB |
Output is correct |
| 7 |
Correct |
331 ms |
66992 KB |
Output is correct |
| 8 |
Correct |
336 ms |
67496 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
51 ms |
8104 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
357 ms |
67500 KB |
Output is correct |
| 2 |
Correct |
355 ms |
68024 KB |
Output is correct |
| 3 |
Correct |
350 ms |
67764 KB |
Output is correct |
| 4 |
Correct |
354 ms |
66976 KB |
Output is correct |
| 5 |
Correct |
350 ms |
67256 KB |
Output is correct |
| 6 |
Correct |
354 ms |
66208 KB |
Output is correct |
| 7 |
Correct |
331 ms |
66992 KB |
Output is correct |
| 8 |
Correct |
336 ms |
67496 KB |
Output is correct |
| 9 |
Correct |
0 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Runtime error |
51 ms |
8104 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
