| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 265583 |
2020-08-15T02:14:07 Z |
caoash |
Park (BOI16_park) |
C++14 |
|
1361 ms |
79672 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair
const int MX = 2005 * 2005;
vector<pair<ll, pair<pi, pi>>> ed; map<pi, int> cc;
template<int SZ> struct DSU{
int p[SZ], sz[SZ];
void init(){
for(int i = 0; i < SZ; i++){
p[i] = i; sz[i] = 1;
}
}
int find(int x){
return p[x] = (p[x] == x ? x : find(p[x]));
}
void merge(int u, int v){
int a = find(u); int b = find(v);
if(a != b){
if(sz[a] < sz[b]){
swap(a,b);
}
p[b] = a;
sz[a] += sz[b];
}
}
};
DSU<MX> dsu; bool ok[2005][4];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, w, h; cin >> n >> m >> w >> h;
vector<pair<pair<ll, ll>, int>> trees(n);
set<pi> pts;
auto dist = [&] (const int &x1, const int &y1, const int &x2, const int &y2) {
return sqrt((ll)(1LL *(x2 - x1) * (ll)(x2 - x1)) + (ll)(1LL * (y2 - y1) * (y2 - y1)));
};
auto add = [&] (const int &x1, const int &y1, const int &x2, const int &y2, const ll &r1, const ll &r2) {
ll ndist = dist(x1, y1, x2, y2) - r1 - r2;
// cout << "adding: " << x1 << " " << y1 << " " << x2 << " " << y2 << " " << ndist << '\n';
ed.pb(mp(ndist, mp(mp(x1, y1), mp(x2, y2))));
};
for (int i = 0; i < n; i++) {
cin >> trees[i].f.f >> trees[i].f.s >> trees[i].s;
pts.insert(mp(trees[i].f.f, trees[i].f.s));
cc[mp(0, trees[i].f.s)] = 3;
cc[mp(trees[i].f.f, h)] = 2;
cc[mp(w, trees[i].f.s)] = 1;
cc[mp(trees[i].f.f, 0)] = 0;
add(trees[i].f.f, trees[i].f.s, 0, trees[i].f.s, trees[i].s, 0);
add(trees[i].f.f, trees[i].f.s, trees[i].f.f, 0, trees[i].s, 0);
add(trees[i].f.f, trees[i].f.s, w, trees[i].f.s, trees[i].s, 0);
add(trees[i].f.f, trees[i].f.s, trees[i].f.f, h, trees[i].s, 0);
}
int cnt = 4;
for (pi x : pts) {
cc[x] = cnt++;
}
assert(cnt <= n + 4);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
add(trees[i].f.f, trees[i].f.s, trees[j].f.f, trees[j].f.s, trees[i].s, trees[j].s);
}
}
vector<pair<pi, int>> qrs;
for (int i = 0; i < m; i++) {
int r, e; cin >> r >> e;
e--;
qrs.pb(mp(mp(2 * r, e), i));
}
sort(all(qrs));
sort(all(ed));
dsu.init();
int p = 0;
memset(ok, true, sizeof(ok));
for (auto v : ed) {
// cout << "ed: " << v.f << "\n";
while (p < sz(qrs) && qrs[p].f.f <= v.f){
bool conn[4][4];
pair<pi, int> curr = qrs[p];
// cout << "qry: " << curr.f.f << " " << curr.f.s << " " << '\n';
for (int i = 0; i < 4; i++) {
conn[i][i] = true;
for (int j = i + 1; j < 4; j++) {
conn[i][j] = (dsu.find(i) == dsu.find(j));
conn[j][i] = conn[i][j];
// cout << "i j conn " << i << " " << j << " " << conn[i][j] << '\n';
}
}
auto bad = [&] (const int &x) {
// if(conn[(x - 1 < 0 ? 3 : x - 1)][x]) cout << "BAD: " << x << '\n';
return conn[(x - 1 < 0 ? 3 : x - 1)][x];
};
for (int i = 0; i < 4; i++) {
if (curr.f.s == i) {
continue;
}
// cout << curr.f.s << " " << i << " " << bad(curr.f.s) << " " << bad(i) << '\n';
if (bad(curr.f.s) || bad(i)) {
ok[curr.s][i] = false;
continue;
}
bool upok = conn[0][2];
bool sok = conn[1][3];
// cout << "i, curr.f.s, upok, sok: " << i << " " << curr.f.s << " " << upok << " " << sok << '\n';
if (abs(curr.f.s - i) == 2) {
if (upok || sok) {
ok[curr.s][i] = false;
continue;
}
}
else if(curr.f.s + i == 3) {
if (sok) {
ok[curr.s][i] = false;
continue;
}
}
else {
if (upok) {
ok[curr.s][i] = false;
}
}
}
++p;
if (p >= sz(qrs)) break;
}
// cout << "merging: " << v.s.f.f << " " << v.s.f.s << " " << v.s.s.f << " " << v.s.s.s << '\n';
// cout << "merging: " << cc[v.s.f] << " " << cc[v.s.s] << '\n';
assert(cc[v.s.f] <= 2005 && cc[v.s.s] <= 2005);
dsu.merge(cc[v.s.f], cc[v.s.s]);
}
for (int i = 0; i < m; i++) {
string ret = "";
for (int j = 0; j < 4; j++) {
if (ok[i][j]) ret += to_string(j + 1);
}
cout << ret << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1291 ms |
79672 KB |
Output is correct |
| 2 |
Correct |
1361 ms |
79672 KB |
Output is correct |
| 3 |
Correct |
1278 ms |
79672 KB |
Output is correct |
| 4 |
Correct |
1313 ms |
79672 KB |
Output is correct |
| 5 |
Correct |
1321 ms |
79672 KB |
Output is correct |
| 6 |
Correct |
1274 ms |
79672 KB |
Output is correct |
| 7 |
Correct |
1143 ms |
79412 KB |
Output is correct |
| 8 |
Correct |
1153 ms |
79412 KB |
Output is correct |
| 9 |
Correct |
20 ms |
31744 KB |
Output is correct |
| 10 |
Correct |
20 ms |
31736 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
33864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1291 ms |
79672 KB |
Output is correct |
| 2 |
Correct |
1361 ms |
79672 KB |
Output is correct |
| 3 |
Correct |
1278 ms |
79672 KB |
Output is correct |
| 4 |
Correct |
1313 ms |
79672 KB |
Output is correct |
| 5 |
Correct |
1321 ms |
79672 KB |
Output is correct |
| 6 |
Correct |
1274 ms |
79672 KB |
Output is correct |
| 7 |
Correct |
1143 ms |
79412 KB |
Output is correct |
| 8 |
Correct |
1153 ms |
79412 KB |
Output is correct |
| 9 |
Correct |
20 ms |
31744 KB |
Output is correct |
| 10 |
Correct |
20 ms |
31736 KB |
Output is correct |
| 11 |
Incorrect |
86 ms |
33864 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
