| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 531795 |
2022-03-01T14:17:08 Z |
OttoTheDino |
Park (BOI16_park) |
C++17 |
|
586 ms |
49792 KB |
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for (ll i = s; i <= e; ++i)
#define rrep(i,s,e) for (ll i = s; i >= e; --i)
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<ll> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
const ll mx = 2000;
ll par[mx+5], hh[mx+5];
ll get_par (ll u) {
if (par[u]==u) return u;
return get_par(par[u]);
}
void merge (ll u, ll v) {
ll pu = get_par(u), pv = get_par(v);
if (hh[pv]>hh[pu]) swap(pu,pv);
if (hh[pu]==hh[pv]) ++hh[pu];
par[pv] = pu;
}
bool con (ll u, ll v) {
return get_par(u)==get_par(v);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
ll n, m, w, h; cin >> n >> m >> w >> h;
rep (i,1,n+4) par[i] = i;
ll x[n+1], y[n+1], r[n+1];
rep (i,1,n) cin >> x[i] >> y[i] >> r[i];
vector<pair<ll,ii>> upds;
rep (i,1,n) {
rep (j,i+1,n) {
ll lo = 0, hi = 1e9;
ll d = (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);
while (lo<hi) {
ll mid = (lo+hi)/2, s = 2*mid+r[i]+r[j];
if (s*s>d) hi = mid;
else lo = mid+1;
}
upds.pb({lo, {i,j}});
}
upds.pb({(x[i]-r[i])/2+1, {i,n+1}});
upds.pb({(y[i]-r[i])/2+1, {i,n+2}});
upds.pb({(w-x[i]-r[i])/2+1, {i,n+3}});
upds.pb({(h-y[i]-r[i])/2+1, {i,n+4}});
}
sort(all(upds), greater<pair<ll,ii>>());
vector<pair<ii,int>> queries;
rep (i,1,m) {
int R, e; cin >> R >> e;
queries.pb({{R,e},i});
}
string ans[m+1];
sort(all(queries), greater<pair<ii,int>>());
rep (k,1,m) {
int s = queries.back().fi.fi, c = queries.back().fi.se;
while (upds.size() && s>=upds.back().fi) {
upds.pop_back();
int u = upds.back().se.fi, v = upds.back().se.se;
if (!con(u,v)) merge(u,v);
}
bool can[5][5] = {};
rep (i,1,4) rep (j,1,4) can[i][j] = 1;
if (con(n+1,n+2)) rep (i,2,4) can[1][i] = can[i][1] = 0;
if (con(n+2,n+3)) {
rep (i,1,4) {
if (i==2) continue;
can[2][i] = can[i][2] = 0;
}
}
if (con(n+3,n+4)) {
rep (i,1,4) {
if (i==3) continue;
can[3][i] = can[i][3] = 0;
}
}
if (con(n+4,n+1)) {
rep (i,1,4) {
if (i==4) continue;
can[4][i] = can[i][4] = 0;
}
}
if (con(n+4,n+2)) {
can[4][3] = can[3][4] = 0;
can[4][2] = can[2][4] = 0;
can[1][3] = can[3][1] = 0;
can[1][2] = can[2][1] = 0;
}
if (con(n+1,n+3)) {
can[1][4] = can[4][1] = 0;
can[1][3] = can[3][1] = 0;
can[2][4] = can[4][2] = 0;
can[2][3] = can[3][2] = 0;
}
rep (i,1,4) if (can[c][i]) ans[queries.back().se] += to_string(i);
queries.pop_back();
}
rep (i,1,m) cout << ans[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
577 ms |
49792 KB |
Output is correct |
| 2 |
Incorrect |
586 ms |
49780 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
7716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
577 ms |
49792 KB |
Output is correct |
| 2 |
Incorrect |
586 ms |
49780 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
