Submission #2084296


Source Code Expand

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.io.PrintWriter;

public class Main {
    static FastScanner sc = new FastScanner(System.in);
    static PrintWriter out = new PrintWriter(System.out);

    public static final void main(String[] args) {
        new Main().solve();
        out.flush();
    }

    // ========================================================================= //

    public void solve() {
        sc.nextInt(); sc.nextInt(); sc.nextInt();
        int s = 50;
        int k = 2500;
        int sy = sc.nextInt() - 1;
        int sx = sc.nextInt() - 1;
        int[][] board = new int[s][s];
        for (int y = 0; y < s; y++) {
            String row = sc.next();
            for (int x = 0; x < s; x++) {
                char c = row.charAt(x);
                if (c == '#') board[y][x] = -1;
                else board[y][x] = 0;
            }
        }

        int n = sc.nextInt();
        int[] F = new int[n + 1];
        int[] D = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            board[sc.nextInt() - 1][sc.nextInt() - 1] = i;
            F[i] = sc.nextInt();
            D[i] = sc.nextInt();
        }

        ShortestPathSolver sps = new ShortestPathSolver(s);
        StringBuilder ans = new StringBuilder();
        int x = sx, y = sy;
        int[][] costs = new int[s][s];
        int[] path = new int[s * s];
        LOOP:while (n >= 1 && ans.length() < k) {
            int[] result = sps.bellmanford(board, costs, x, y);
            int pathLen = sps.getPath(costs, x, y, result[0], result[1], path);
            for (int i = 0; i < pathLen; i++) {
                int nx = sps.x(path[i]);
                int ny = sps.y(path[i]);

                String dir = "";
                if (nx - x == -1) {
                    dir = "L";
                }
                if (nx - x == 1) {
                    dir = "R";
                }
                if (ny - y == - 1) {
                    dir = "U";
                }
                if (ny - y == 1) {
                    dir = "D";
                }

                assert !dir.equals("");

                if (ans.length() < k) ans.append(dir);
                else break LOOP;

                x = nx;
                y = ny;
            }

            board[y][x] = 0;
            n--;

            assert y == result[1] && x == result[0];
        }
        while (ans.length() < k) {
            ans.append("-");
        }
        System.out.println(ans.toString());
    }
}

class ShortestPathSolver {
    private final int n, mask;
    private int[] queue;

    public ShortestPathSolver(int n) {
        this.n = n;
        this.mask = (1 << 15) - 1;
        this.queue = new int[n * n * 4];
    }

    // 単一始点複数終点
    //     0: 通行可
    //    -1: 通行不可
    // 1以上: 終点
    public int[] bellmanford(int[][] board, int[][] costs, int sx, int sy) {
        for (int i = 0; i < n; i++) Arrays.fill(costs[i], Integer.MAX_VALUE);

        int headIdx = 0, tailIdx = 0, bs, ny, nx;
        queue[tailIdx++] = p(sx, sy);
        costs[sy][sx] = 0;

        int minCost = Integer.MAX_VALUE;
        int minCostP = -1;

        while (headIdx != tailIdx) {
            int p = queue[headIdx++];
            int y = y(p);
            int x = x(p);
            int nextc = costs[y][x] + 1;

            if (nextc >= minCost)
                continue;

            if (y >= 1 && nextc < costs[ny = y - 1][x]) {
                if ((bs = board[ny][x]) > 0) {
                    minCost = nextc;
                    minCostP = p(x, ny);
                    costs[ny][x] = nextc;
                }
                else if (bs == 0) {
                    queue[tailIdx++] = p(x, ny);
                    costs[ny][x] = nextc;
                }
            }

            if (x >= 1 && nextc < costs[y][nx = x - 1]) {
                if ((bs = board[y][nx]) > 0) {
                    minCost = nextc;
                    minCostP = p(nx, y);
                    costs[y][nx] = nextc;
                }
                else if (bs == 0) {
                    queue[tailIdx++] = p(nx, y);
                    costs[y][nx] = nextc;
                }
            }

            if (y < n - 1 && nextc < costs[ny = y + 1][x]) {
                if ((bs = board[ny][x]) > 0) {
                    minCost = nextc;
                    minCostP = p(x, ny);
                    costs[ny][x] = nextc;
                }
                else if (bs == 0) {
                    queue[tailIdx++] = p(x, ny);
                    costs[ny][x] = nextc;
                }
            }

            if (x < n - 1 && nextc < costs[y][nx = x + 1]) {
                if ((bs = board[y][nx]) > 0) {
                    minCost = nextc;
                    minCostP = p(nx, y);
                    costs[y][nx] = nextc;
                }
                else if (bs == 0) {
                    queue[tailIdx++] = p(nx, y);
                    costs[y][nx] = nextc;
                }
            }
        }

        return new int[] {x(minCostP), y(minCostP)};
    }

    // 重みなしのパスを返す
    // pathに終点からの最短経路を格納しパスの長さを返す
    public int getPath(int[][] costs, int sx, int sy, int ex, int ey, int[] path) {
        int pathLen = 0;
        int x = ex, y = ey, nx, ny;
        while (p(x, y) != p(sx, sy)) {
            queue[pathLen++] = p(x, y);
            int nextc = costs[y][x] - 1;

            assert nextc >= 0;

            if (y >= 1 && costs[ny = y - 1][x] == nextc) {
                y = ny;
                continue;
            }
            if (x >= 1 && costs[y][nx = x - 1] == nextc) {
                x = nx;
                continue;
            }
            if (y < n - 1 && costs[ny = y + 1][x] == nextc) {
                y = ny;
                continue;
            }
            if (x < n - 1 && costs[y][nx = x + 1] == nextc) {
                x = nx;
            }
        }

        int pathIdx = 0;
        for (int i = pathLen - 1; i >= 0; i--) {
            path[pathIdx++] = queue[i];
        }

        return pathLen;
    }

    public int p(int x, int y) { return (y << 15) | x; }
    public int x(int p) { return p & mask; }
    public int y(int p) { return (p >> 15); }
}

class FastScanner {
    public static void main(String[] args) {
        FastScanner f = new FastScanner(System.in);
        while (true) {
            System.out.println(f.nextInt());
        }
    }
    private final InputStream in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }
        else {
            ptr = 0;
            try { buflen = in.read(buffer); }
            catch (IOException e) { e.printStackTrace(); }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; }
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; }
    private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; }
    private boolean hasNext() { skipUnprintable(); return hasNextByte(); }
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public String nextLine() {
        if (!hasNext()) return null;
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (b != -1 && b != '\n') {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && '9' <= b) {
                n *= 10;
                n += b - '0';
            }
            else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            }
            else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        if (!hasNext()) throw new NoSuchElementException();
        int n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }
            else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            }
            else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public FastScanner(String str) {
        this(new ByteArrayInputStream(str.getBytes()));
    }
    public FastScanner(InputStream in) {
        this.in = in;
    }
}

Submission Info

Submission Time
Task B - Food Collector
User suikkee
Language Java8 (OpenJDK 1.8.0)
Score 14904
Code Size 9983 Byte
Status AC
Exec Time 88 ms
Memory 21844 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 1521 / 20000 1725 / 20000 1461 / 20000 1009 / 20000 1644 / 20000 1861 / 20000 1518 / 20000 1355 / 20000 1049 / 20000 1761 / 20000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 84 ms 20436 KB
subtask_01_02.txt AC 88 ms 21716 KB
subtask_01_03.txt AC 85 ms 21588 KB
subtask_01_04.txt AC 86 ms 21460 KB
subtask_01_05.txt AC 86 ms 19028 KB
subtask_01_06.txt AC 86 ms 19668 KB
subtask_01_07.txt AC 84 ms 18260 KB
subtask_01_08.txt AC 86 ms 19796 KB
subtask_01_09.txt AC 84 ms 21844 KB
subtask_01_10.txt AC 84 ms 21716 KB