# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
274876 |
2020-08-19T19:11:40 Z |
rqi |
Park (BOI16_park) |
C++14 |
|
2500 ms |
19960 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define mp make_pair
#define f first
#define s second
#define pb push_back
const int MOD = 1000000007;
const int mx = 100005;
int n, m;
ll w, h;
ll k;
ll x[mx];
ll y[mx];
ll r[mx];
ll R[mx];
int e[mx];
pair<vi, vi> sep[7];
pi connec[7];
int his[7]; //lowest value to make it connected
int comp[mx];
vi adj[mx];
void ae(int a, int b){
adj[a].pb(b); adj[b].pb(a);
}
void dfs(int node, int val){
if(comp[node] != 0) return;
comp[node] = val;
for(auto u: adj[node]){
dfs(u, val);
}
}
bool works(int ind, ll mid){
for(int i = 1; i <= n+4; i++){
comp[i] = 0;
adj[i].clear();
}
//add all the edges
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) < (r[i]+r[j]+2*mid)*(r[i]+r[j]+2*mid)){
ae(i, j);
}
}
}
for(int i = 1; i <= n; i++){
ll xlo = x[i]-r[i]-2*mid;
ll xhi = x[i]+r[i]+2*mid;
ll ylo = y[i]-r[i]-2*mid;
ll yhi = y[i]+r[i]+2*mid;
if(xlo < 0){
ae(i, n+4);
}
if(xhi > w){
ae(i, n+2);
}
if(ylo < 0){
ae(i, n+1);
}
if(yhi > h){
ae(i, n+3);
}
}
for(int i = 1; i <= n+4; i++){
if(comp[i] != 0) continue;
dfs(i, i); //node, val
}
if(comp[connec[ind].f] == comp[connec[ind].s]) return 1;
return 0;
}
void findHis(){
for(int i = 1; i <= 6; i++){
ll lo = 0;
ll hi = MOD;
while(lo < hi){
ll mid = (lo+hi)/2;
if(works(i, mid)){
hi = mid;
}
else lo = mid+1;
}
his[i] = lo;
}
}
int main(){
cin >> n >> m;
cin >> w >> h;
sep[1] = mp(vi{1}, vi{2, 3, 4});
sep[2] = mp(vi{2}, vi{1, 3, 4});
sep[3] = mp(vi{3}, vi{1, 2, 4});
sep[4] = mp(vi{4}, vi{1, 2, 3});
sep[5] = mp(vi{1, 4}, vi{2, 3});
sep[6] = mp(vi{1, 2}, vi{3, 4});
connec[1] = mp(n+1, n+4);
connec[2] = mp(n+1, n+2);
connec[3] = mp(n+2, n+3);
connec[4] = mp(n+3, n+4);
connec[5] = mp(n+1, n+3);
connec[6] = mp(n+2, n+4);
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i] >> r[i];
}
for(int i = 1; i <= m; i++){
cin >> R[i] >> e[i];
k = max(k, r[i]);
}
findHis();
for(int i = 1; i <= m; i++){
vector<bool> v(5, true);
for(int j = 1; j <= 6; j++){
if(R[i] >= his[j]){
for(auto u: sep[j].f){
if(u == e[i]){
for(auto z: sep[j].s){
v[z] = false;
}
}
}
for(auto u: sep[j].s){
if(u == e[i]){
for(auto z: sep[j].f){
v[z] = false;
}
}
}
}
}
for(int j = 1; j <= 4; j++){
if(v[j] == true) cout << j;
}
cout << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1057 ms |
19960 KB |
Output is correct |
2 |
Correct |
1063 ms |
19812 KB |
Output is correct |
3 |
Correct |
1063 ms |
19688 KB |
Output is correct |
4 |
Correct |
1095 ms |
19704 KB |
Output is correct |
5 |
Correct |
1086 ms |
19872 KB |
Output is correct |
6 |
Correct |
1057 ms |
19756 KB |
Output is correct |
7 |
Execution timed out |
2563 ms |
19064 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
5624 KB |
Output is correct |
2 |
Correct |
140 ms |
5496 KB |
Output is correct |
3 |
Correct |
152 ms |
5436 KB |
Output is correct |
4 |
Correct |
150 ms |
5584 KB |
Output is correct |
5 |
Correct |
141 ms |
5496 KB |
Output is correct |
6 |
Correct |
169 ms |
5500 KB |
Output is correct |
7 |
Correct |
135 ms |
5292 KB |
Output is correct |
8 |
Correct |
134 ms |
5368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1057 ms |
19960 KB |
Output is correct |
2 |
Correct |
1063 ms |
19812 KB |
Output is correct |
3 |
Correct |
1063 ms |
19688 KB |
Output is correct |
4 |
Correct |
1095 ms |
19704 KB |
Output is correct |
5 |
Correct |
1086 ms |
19872 KB |
Output is correct |
6 |
Correct |
1057 ms |
19756 KB |
Output is correct |
7 |
Execution timed out |
2563 ms |
19064 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |