| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 346451 |
2021-01-09T19:00:59 Z |
dapig |
Park (BOI16_park) |
Java 11 |
|
166 ms |
12504 KB |
import java.io.*;
import java.util.*;
class SortArr implements Comparator<int[]> {
@Override
public int compare(int[] o1, int[] o2) {
int ans = o1[0]-o2[0];
if (ans == 0) return o2[3]-o1[3];
return ans;
}
}
class Park {
public static void main(String[] args) throws IOException {
Park obj = new Park();
obj.doStuff();
}
int[] p, r; boolean[][] v; boolean[][] full;
boolean[][] poss;
void setdsu(int l) {
p = new int[l]; r = new int[l]; v = new boolean[l][4];
for (int i = 0; i < p.length; i++) {
p[i] = i; r[i] = 1;
}
full = new boolean[4][4];
}
int fpar(int n) {
if (p[n] != n) p[n] = fpar(p[n]);
return p[n];
}
void upar(int a, int b) {
a = fpar(a); b = fpar(b); if (a==b)return;
if (r[b]>r[a]) {int temp=b;b=a;a=temp;}
p[b]=a;r[a]+=r[b];
for (int i = 0; i < v[0].length; i++) {
v[a][i] = (v[a][i]||v[b][i]);
for (int j = i-1; j >= 0; j--) {
full[j][i] = v[a][j]&&v[a][i];
full[i][j] = v[a][j]&&v[a][i];
}
}
}
void uedge(int n, int type) {
n = fpar(n);
type = -1-type;
v[n][type] = true;
for (int j = 0; j < 4; j++) { if (j==type) continue;
full[j][type] = v[n][j]&&v[n][type];
full[type][j] = v[n][j]&&v[n][type];
}
}
boolean test(int r) {
return !(full[r][0]||full[r][1]||full[r][2]||full[r][3]);
}
boolean test2(int b) {
return !(full[(b+3)%4][b]||full[(b+3)%4][(b+1)%4]||
full[b][(b+2)%4]||full[(b+1)%4][(b+2)%4]);
}
void process(int id, int e) {
int right = e;
int left = (e+3)%4;
poss[id][e] = true;
if (test(right)) poss[id][(e+1)%4] = true;
if (test(left)) poss[id][left] = true;
if (test2((e+2)%4)) poss[id][(e+2)%4] = true;
}
private void doStuff() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int trees = Integer.parseInt(st.nextToken());
int visitors = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
int width = Integer.parseInt(st.nextToken()); // bottom left is 0,0
int height = Integer.parseInt(st.nextToken());
setdsu(trees);
int[][] treeArr = new int[trees][3]; // x, y, r
PriorityQueue<int[]> pq = new PriorityQueue<>(new SortArr());
for (int i = 0; i < trees; i++) {
st = new StringTokenizer(br.readLine());
treeArr[i] = new int[] {
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken())
};
for (int j = i-1; j >= 0; j--) {
double xdist = treeArr[i][0]-treeArr[j][0];
double ydist = treeArr[i][1]-treeArr[j][1];
int dist = (int) Math.floor(Math.sqrt(xdist*xdist+ydist*ydist));
dist -= (treeArr[i][2]+treeArr[j][2]);
pq.add(new int[] {dist, j, i, 0});
}
pq.add(new int[] {treeArr[i][0]-treeArr[i][2], i, -4, 1});
pq.add(new int[] {treeArr[i][1]-treeArr[i][2], i, -1, 1});
pq.add(new int[] {width-treeArr[i][0]-treeArr[i][2], i, -2, 1});
pq.add(new int[] {height-treeArr[i][1]-treeArr[i][2], i, -3, 1});
}
for (int i = 0; i < visitors; i++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
pq.add(new int[] {2*r, -1-i, Integer.parseInt(st.nextToken()), 2});
}
br.close();
poss = new boolean[visitors][4];
while (!pq.isEmpty()) {
int[] next = pq.poll();
if (next[1] < 0) {
int id = -1-next[1];
int e = next[2]-1;
process(id, e);
} else if (next[2] < 0) {
uedge(next[1], next[2]);
} else {
upar(next[1], next[2]);
}
}
for (boolean[] i : poss) {
for (int j = 0; j < 4; j++) {
if (i[j]) System.out.print(j+1);
}
System.out.println();
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
166 ms |
12344 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
162 ms |
12504 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
166 ms |
12344 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
