| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 384869 |
2021-04-02T14:22:18 Z |
innocentkitten |
Park (BOI16_park) |
C++14 |
|
2500 ms |
66192 KB |
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define H 2021
using namespace std;
typedef pair<long long int,long long int> pii;
typedef pair<pii,int> circ;
int N,M,W,L;
circ C[H]; // nodes 2001, 2002, 2003, 2004 are SENW borders
vector<pii> process;
vector<circ> offline;
int ret[100010];
int S[H];
int P[H];
bool adj[4][4];
bool reach[5][5];
bool sz(circ a, circ b) {
return a.f.f < b.f.f;
}
bool re(circ a, circ b) {
return a.s < b.s;
}
int eval(int a, int b) {
if (b > 2000) return eval(b,a);
if (a == 2001) return C[b].f.s-C[b].s;
if (a == 2002) return W-C[b].f.f-C[b].s;
if (a == 2003) return L-C[b].f.s-C[b].s;
if (a == 2004) return C[b].f.f-C[b].s;
return (int)(sqrt((C[a].f.f-C[b].f.f)*(C[a].f.f-C[b].f.f)
+(C[a].f.s-C[b].f.s)*(C[a].f.s-C[b].f.s))-C[a].s-C[b].s);
// not sure if they want floor or ceil, so i'm keeping it
// this way for now
}
bool comp(pii a, pii b){
return eval(a.f,a.s)<eval(b.f,b.s);
}
int pp(int x) {
if (P[x]==x) return x;
return (P[x] = pp(P[x]));
}
void un(int a, int b) {
a = pp(a);
b = pp(b);
if (a == b) return;
if (S[a] > S[b]) swap(a,b);
S[b] += S[a];
P[a] = b;
}
int main() {
cin>>N>>M>>W>>L;
for (int i = 0; i < H; i++) {
S[i] = 1; P[i] = i;
}
for (int i = 0; i < N; i++) {
int a,b,r; cin>>a>>b>>r;
C[i]=mp(mp(a,b),r);
for (int j = 2001; j < 2005; j++) {
process.pb(mp(j,i));
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == j) continue;
process.pb(mp(i,j));
}
}
sort(process.begin(),process.end(),comp);
for (int i = 0; i < M; i++) {
int s,p; cin >> s >> p;
offline.pb(mp(mp(s,p),i));
}
sort(offline.begin(),offline.end(),sz);
int point=0;
if (N > 1000) throw 1;
for (int i = 0; i < M; i++) {
circ quer = offline[i];
while ((point < process.size())
&& ((eval(process[point].f,process[point].s))
< 2*quer.f.f)) {
un(process[point].f,process[point].s);
point++;
}
for (int x = 0; x < 4; x++) {
for (int y = x+1; y < 4; y++) {
adj[x][y]=(pp(x+2001)==pp(y+2001));
adj[y][x]=adj[x][y];
}
}
reach[1][1] = true;
reach[2][2] = true;
reach[3][3] = true;
reach[4][4] = true;
reach[1][2] = !(adj[0][1]||adj[0][2]||adj[0][3]);
reach[2][1] = reach[1][2];
reach[2][3] = !(adj[1][0]||adj[1][2]||adj[1][3]);
reach[3][2] = reach[2][3];
reach[3][4] = !(adj[2][0]||adj[2][1]||adj[2][3]);
reach[4][3] = reach[3][4];
reach[4][1] = !(adj[3][0]||adj[3][1]||adj[3][2]);
reach[1][4] = reach[4][1];
reach[1][3] = !(adj[0][2]||adj[0][3]||adj[1][2]||adj[1][3]);
reach[3][1] = reach[1][3];
reach[2][4] = !(adj[0][1]||adj[0][2]||adj[3][1]||adj[3][2]);
reach[4][2] = reach[2][4];
for (int x = 1; x < 5; x++) {
if (reach[quer.f.s][x]) cout << x;
}
cout << endl;
}
}
Compilation message
park.cpp: In function 'int main()':
park.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | while ((point < process.size())
| ~~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2584 ms |
66192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
340 ms |
5260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2584 ms |
66192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
