| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 143172 | mmaxio | Sky Walking (IOI19_walk) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.*;
import java.util.*;
public class walk {
static class Point {
int x, y;
int id;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
boolean sameAs(Point o) {
return x == o.x && y == o.y;
}
@Override
public String toString() {
return "(" + x + ", " + y + ")";
}
}
static class Segment implements Comparable<Segment> {
Point p, q;
public Segment(Point p, Point q) {
this.p = p;
this.q = q;
}
@Override
public int compareTo(Segment o) {
return Integer.compare(p.x, o.p.x);
}
@Override
public String toString() {
if (p.x == q.x) {
return String.format("vert at x = %s, y = %s..%s", p.x, p.y,
q.y);
} else {
return String
.format("hor at y = %s, x = %s..%s", p.y, p.x, q.x);
}
}
boolean contains(Point pt) {
return p.x <= pt.x && pt.x <= q.x && p.y <= pt.y && pt.y <= q.y;
}
}
static class Event implements Comparable<Event> {
int y;
/**
* 0 - horizontal 1 - end of vertical 2 - start of vertical
*/
int type;
Segment seg;
public Event(int y, int type, Segment seg) {
this.y = y;
this.type = type;
this.seg = seg;
}
@Override
public int compareTo(Event o) {
if (y != o.y) {
return y < o.y ? -1 : 1;
}
return Integer.compare(type, o.type);
}
}
static final int MAX_POINTS = 6_000_000;
static final long INF = Long.MAX_VALUE / 5;
Point[] lst = new Point[MAX_POINTS];
int lstSz = 0;
Point[] horEnds;
int horEndsSz = 0;
Point[] verEnds;
int verEndsSz = 0;
Random rng = new Random();
long solve(int[] x1s, int[] y1s, int[] x2s, int[] y2s, int fromX, int toX, int fromY, int toY) {
int n = x1s.length;
// int n = 20000;
Segment[] a = new Segment[n];
int[] allX = new int[2 * n];
horEnds = new Point[2 * n];
verEnds = new Point[2 * n];
Event[] verEvs = new Event[2 * n];
int verEvsSz = 0;
Event[] horEvs = new Event[n];
int horEvsSz = 0;
for (int i = 0; i < n; i++) {
int x1 = x1s[i];
int y1 = y1s[i];
int x2 = x2s[i];
int y2 = y2s[i];
// int x1, y1, x2, y2;
// if (i < n / 2) {
// x1 = i;
// y1 = 0;
// x2 = i;
// y2 = n / 2 - 1;
// } else {
// x1 = 0;
// y1 = i - n / 2;
// x2 = n / 2 - 1;
// y2 = i - n / 2;
// }
// int x1, y1, x2, y2;
// if (rng.nextBoolean()) {
// x1 = x2 = rng.nextInt(1_000_000_000);
// y1 = rng.nextInt(1_000_000_000);
// y2 = rng.nextInt(1_000_000_000);
// } else {
// y1 = y2 = rng.nextInt(1_000_000_000);
// x1 = rng.nextInt(1_000_000_000);
// x2 = rng.nextInt(1_000_000_000);
// }
allX[2 * i] = x1;
allX[2 * i + 1] = x2;
Point p = new Point(x1, y1);
Point q = new Point(x2, y2);
// System.err.println(p + " - " + q);
lst[lstSz++] = p;
lst[lstSz++] = q;
if (p.x + p.y > q.x + q.y) {
Point tmp = p;
p = q;
q = tmp;
}
a[i] = new Segment(p, q);
if (p.x == q.x) {
verEvs[verEvsSz++] = new Event(q.y, 2, a[i]);
verEvs[verEvsSz++] = new Event(p.y, 1, a[i]);
verEnds[verEndsSz++] = p;
verEnds[verEndsSz++] = q;
} else {
horEvs[horEvsSz++] = new Event(p.y, 0, a[i]);
horEnds[horEndsSz++] = p;
horEnds[horEndsSz++] = q;
}
}
verEvs = Arrays.copyOf(verEvs, verEvsSz);
horEvs = Arrays.copyOf(horEvs, horEvsSz);
Arrays.sort(verEvs, new Comparator<Event>() {
@Override
public int compare(Event o1, Event o2) {
return Integer.compare(o1.seg.p.x, o2.seg.p.x);
}
});
Arrays.sort(horEvs);
horEnds = Arrays.copyOf(horEnds, horEndsSz);
Arrays.sort(horEnds, byYThenX);
verEnds = Arrays.copyOf(verEnds, verEndsSz);
Arrays.sort(verEnds, byXThenY);
allX = unique(allX);
int cntX = allX.length;
K = (int) Math.sqrt(cntX);
Segment[] hors = new Segment[n];
int horsSz = 0;
TreeSet<Segment> vers = new TreeSet<>();
Event[] stripEvs = new Event[2 * n];
int stripEvsSz = 0;
int ptrFrom = 0;
for (int i = 0; i < cntX; i += K) {
// System.err.println(i);
int left = allX[i];
int right = allX[Math.min(i + K, cntX - 1)];
horsSz = 0;
vers.clear();
while (ptrFrom < verEvsSz && verEvs[ptrFrom].seg.p.x < left) {
ptrFrom++;
}
int ptrStrip = ptrFrom;
stripEvsSz = 0;
while (ptrStrip < verEvsSz && verEvs[ptrStrip].seg.p.x <= right) {
stripEvs[stripEvsSz++] = verEvs[ptrStrip++];
}
Arrays.sort(stripEvs, 0, stripEvsSz);
int horPtr = 0;
int verPtr = 0;
while (horPtr < horEvsSz || verPtr < stripEvsSz) {
Event curHorEv = horPtr == horEvsSz ? null : horEvs[horPtr];
Event curVerEv = verPtr == stripEvsSz ? null : stripEvs[verPtr];
if (curVerEv == null
|| (curHorEv != null && curHorEv.y < curVerEv.y)) {
Event ev = curHorEv;
int xFrom = ev.seg.p.x;
int xTo = ev.seg.q.x;
if (xTo < left || xFrom > right) {
horPtr++;
continue;
}
if (xFrom <= left && xTo >= right) {
hors[horsSz++] = ev.seg;
} else {
flushGrid(hors, horsSz, vers, ev.seg);
horsSz = 0;
}
horPtr++;
} else {
Event ev = curVerEv;
flushGrid(hors, horsSz, vers, null);
horsSz = 0;
if (ev.type == 1) {
vers.add(ev.seg);
} else {
vers.remove(ev.seg);
}
verPtr++;
}
}
flushGrid(hors, horsSz, vers, null);
}
// int fromX = nextInt();
// int fromY = nextInt();
// int toX = nextInt();
// int toY = nextInt();
// int fromX = a[0].p.x;
// int fromY = a[0].p.y;
// int toX = a[1].q.x;
// int toY = a[1].q.y;
// int fromX = a[0].p.x;
// int fromY = a[0].p.y;
// int toX = -1;
// int toY = -1;
Point source = new Point(fromX, fromY);
Point sink = new Point(toX, toY);
lst[lstSz++] = source;
lst[lstSz++] = sink;
for (int i = 0; i < n; i++) {
if (a[i].contains(source) || a[i].contains(sink)) {
for (int j = 0; j < n; j++) {
Point tmp = inter(a[i], a[j]);
if (tmp != null) {
lst[lstSz++] = tmp;
}
tmp = inter(a[j], a[i]);
if (tmp != null) {
lst[lstSz++] = tmp;
}
}
}
}
System.err.println("scanline "
+ (System.currentTimeMillis() - startTime) + " ms");
buildGraph(sink);
System.err.println("graph built " + (System.currentTimeMillis() - startTime)
+ " ms");
return shortestPath(source, sink);
// System.err.println("shortest path found "
// + (System.currentTimeMillis() - startTime) + " ms");
}
static Comparator<Point> byXThenY = new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
if (o1.x != o2.x) {
return o1.x < o2.x ? -1 : 1;
}
return Integer.compare(o1.y, o2.y);
}
};
static Comparator<Point> byYThenX = new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
if (o1.y != o2.y) {
return o1.y < o2.y ? -1 : 1;
}
return Integer.compare(o1.x, o2.x);
}
};
int[] gHead;
int[] gNext;
int[] gTo;
int[] gLen;
int gSz;
long[] heur;
void buildGraph(Point sink) {
Arrays.sort(lst, 0, lstSz, byXThenY);
int sz = 1;
Point last = lst[0];
for (int i = 1; i < lstSz; i++) {
Point ith = lst[i];
if (!ith.sameAs(last)) {
lst[sz++] = ith;
last = ith;
}
}
// out.println("unique lst " + (System.currentTimeMillis() - startTime)
// + " ms");
lst = Arrays.copyOf(lst, sz);
heur = new long[sz];
for (int i = 0; i < sz; i++) {
lst[i].id = i;
heur[i] = manhDist(lst[i], sink);
}
// System.err.println(Arrays.toString(lst));
// out.println("size = " + sz);
// g = new int[sz][8];
// dblDeg = new int[sz * 8];
gHead = new int[sz];
gNext = new int[sz * 4];
gTo = new int[sz * 4];
gLen = new int[sz * 4];
gSz = 0;
Arrays.fill(gHead, -1);
// System.err.println(verEnds.length + " - verEnds.length");
int ptr = 0;
for (int i = 0; i < sz - 1; i++) {
while (ptr < verEnds.length
&& byXThenY.compare(verEnds[ptr], lst[i]) <= 0) {
ptr += 2;
}
if (ptr == 0) {
continue;
}
if (byXThenY.compare(lst[i + 1], verEnds[ptr - 1]) <= 0) {
connectNodes(lst[i], lst[i + 1]);
}
}
// out.println("vertical segments " + (System.currentTimeMillis() -
// startTime) + " ms");
Arrays.sort(lst, byYThenX);
ptr = 0;
for (int i = 0; i < sz - 1; i++) {
while (ptr < horEnds.length
&& byYThenX.compare(horEnds[ptr], lst[i]) <= 0) {
ptr += 2;
}
if (ptr == 0) {
continue;
}
if (byYThenX.compare(lst[i + 1], horEnds[ptr - 1]) <= 0) {
connectNodes(lst[i], lst[i + 1]);
}
}
// out.println("horizontal segments " + (System.currentTimeMillis() -
// startTime) + " ms");
}
static class Distance implements Comparable<Distance> {
long dist;
int v;
long key;
@Override
public int compareTo(Distance o) {
return Long.compare(key, o.key);
}
public Distance(long dist, int v, long key) {
this.dist = dist;
this.v = v;
this.key = key;
}
}
static int manhDist(Point a, Point b) {
return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}
long shortestPath(Point source, Point sink) {
int n = lst.length;
long[] d = new long[n];
Arrays.fill(d, INF);
int s = -1;
int t = -1;
for (int i = 0; i < n; i++) {
if (lst[i].sameAs(source)) {
s = lst[i].id;
}
if (lst[i].sameAs(sink)) {
t = lst[i].id;
}
}
boolean[] vis = new boolean[n];
int[] que = new int[n];
int head = 0, tail = 0;
boolean canReach = false;
que[tail++] = s;
vis[s] = true;
while (head < tail) {
int v = que[head++];
if (v == t) {
canReach = true;
break;
}
for (int idx = gHead[v]; idx != -1; idx = gNext[idx]) {
int u = gTo[idx];
if (!vis[u]) {
vis[u] = true;
que[tail++] = u;
}
}
}
if (!canReach) {
return -1;
}
PriorityQueue<Distance> q = new PriorityQueue<>();
d[s] = 0;
q.add(new Distance(0, s, heur[s]));
while (!q.isEmpty()) {
Distance tmp = q.poll();
long dist = tmp.dist;
int v = tmp.v;
if (v == t) {
return dist;
}
if (d[v] != dist) {
continue;
}
for (int idx = gHead[v]; idx != -1; idx = gNext[idx]) {
int u = gTo[idx];
int len = gLen[idx];
if (d[u] > dist + len) {
d[u] = dist + len;
q.add(new Distance(d[u], u, d[u] + heur[u]));
}
}
}
throw new AssertionError();
}
void connectNodes(Point a, Point b) {
// System.err.println(a + " " + b);
int len = Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
int v = a.id;
int u = b.id;
gTo[gSz] = u;
gLen[gSz] = len;
gNext[gSz] = gHead[v];
gHead[v] = gSz++;
gTo[gSz] = v;
gLen[gSz] = len;
gNext[gSz] = gHead[u];
gHead[u] = gSz++;
}
void flushGrid(Segment[] hors, int horsSz, TreeSet<Segment> vers,
Segment free) {
// System.err.println(hors);
// System.err.println(vers);
// System.err.println(free);
// System.err.println("----------");
if (horsSz != 0 && !vers.isEmpty()) {
Segment low = hors[0];
Segment high = hors[horsSz - 1];
Segment left = vers.first();
Segment right = vers.last();
// in these loops we don't check if inter returns null
// because they shouldn't and we'll get an exception
// while sorting list of points if we'll get null in the list
for (int i = 0; i < horsSz; i++) {
Segment seg = hors[i];
lst[lstSz++] = inter(seg, left);
if (left != right) {
lst[lstSz++] = inter(seg, right);
}
}
for (Segment seg : vers) {
lst[lstSz++] = inter(low, seg);
if (low != high) {
lst[lstSz++] = inter(high, seg);
}
}
}
if (free == null) {
return;
}
// and here it might not intersect
for (Segment seg : vers) {
Point tmp = inter(free, seg);
if (tmp != null) {
lst[lstSz++] = tmp;
}
}
}
Point inter(Segment hor, Segment ver) {
if (hor.p.y != hor.q.y) {
return null;
}
if (ver.p.x != ver.q.x) {
return null;
}
int resX = ver.p.x;
int resY = hor.p.y;
if (hor.p.x <= resX && resX <= hor.q.x && ver.p.y <= resY
&& resY <= ver.q.y) {
return new Point(resX, resY);
}
return null;
}
// int K = 200;
int K;
int[] unique(int[] a) {
Arrays.sort(a);
int sz = 1;
for (int i = 1; i < a.length; i++) {
if (a[i] != a[sz - 1]) {
a[sz++] = a[i];
}
}
return Arrays.copyOf(a, sz);
}
walk() {
// String input = genAlmostGrid(5000);
// System.err.println(input);
// br = new BufferedReader(new InputStreamReader(System.in));
// br = new BufferedReader(new StringReader(input));
// out = new PrintWriter(System.out);
// solve();
// out.close();
}
String genAlmostGrid(int n) {
StringBuilder sb = new StringBuilder();
sb.append(n * 4);
sb.append('\n');
for (int i = 0; i < n; i++) {
int mid = 1 + rng.nextInt(n - 3);
sb.append(String.format("%d %d %d %d\n", i, 0, i, mid));
sb.append(String.format("%d %d %d %d\n", i, mid + 1, i, n - 1));
}
for (int i = 0; i < n; i++) {
int mid = 1 + rng.nextInt(n - 3);
sb.append(String.format("%d %d %d %d\n", 0, i, mid, i));
sb.append(String.format("%d %d %d %d\n", mid + 1, i, n - 1, i));
}
sb.append(String.format("%d %d %d %d", rng.nextInt(n), rng.nextInt(n),
rng.nextInt(n), rng.nextInt(n)));
return sb.toString();
}
long startTime = System.currentTimeMillis();
public static void main(String[] args) throws IOException {
new walk();
}
String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (Exception e) {
eof = true;
return null;
}
}
return st.nextToken();
}
String nextString() {
try {
return br.readLine();
} catch (IOException e) {
eof = true;
return null;
}
}
int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
long nextLong() throws IOException {
return Long.parseLong(nextToken());
}
double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
long min_distance(int[] x, int[] h, int[] orig_l, int[] orig_r, int[] orig_y, int s, int g) {
int n = x.length + orig_l.length;
int[] x1s = new int[n];
int[] y1s = new int[n];
int[] x2s = new int[n];
int[] y2s = new int[n];
int ptr = 0;
for (int i = 0; i < x.length; i++) {
x1s[ptr] = x[i];
y1s[ptr] = 0;
x2s[ptr] = x[i];
y2s[ptr] = h[i];
ptr++;
}
for (int i = 0; i < orig_l.length; i++) {
x1s[ptr] = x[orig_l[i]];
y1s[ptr] = orig_y[i];
x2s[ptr] = x[orig_r[i]];
y2s[ptr] = orig_y[i];
ptr++;
}
int fromX = x[s];
int fromY = 0;
int toX = x[g];
int toY = 0;
return solve(x1s, y1s, x2s, y2s, fromX, fromY, toX, toY);
}
}